Robbins' theorem: Difference between revisions

Revision as of 10:56, 27 January 2016

Latest revision as of 19:55, 20 August 2025

(14 intermediate revisions by 9 users not shown)

Line 1:

{{short description|Equivalence between strongly orientable graphs and bridgeless graphs}}

{{otheruses4|Robbins' theorem in graph theory|Robin's theorem in number theory|divisor function}}

In [[graph theory]], '''Robbins' theorem''', named after {{harvs|first=Herbert|last=Robbins|authorlink=Herbert Robbins|year=1939|txt}}, states that the graphs that have [[strong orientation]]s are exactly the [[k-edge-connected graph|2-edge-connected graphs]]. That is, it is possible to choose a direction for each edge of an [[undirected graph]] {{mvar|G}}, turning it into a [[directed graph]] that has a path from every vertex to every other vertex, if and only if {{mvar|G}} is [[connected graph|connected]] and has no [[Bridge (graph theory)|bridge]].

==Orientable graphs==

Line 9 ⟶ 10:

If a graph has a bridge, then it cannot be strongly orientable, for no matter which orientation is chosen for the bridge there will be no path from one of the two endpoints of the bridge to the other.

In the other direction, it is necessary to show that every connected bridgeless graph can be strongly oriented. As Robbins proved, every such graph has a partition into a sequence of subgraphs called "ears", in which the first subgraph in the sequence is a cycle and each subsequent subgraph is a path, with the two path endpoints both belonging to earlier ears in the sequence. (The two path endpoints may be equal, in which case the subgraph is a cycle.) Orienting the edges within each ear so that it forms a directed cycle or a directed path leads to a strongly connected orientation of the overall graph.<ref>{{harvtxt|Gross|Yellen|2006}}.</ref>

==Related results==

Line 15 ⟶ 16:

==Algorithms and complexity==

A strong orientation of a given bridgeless undirected graph may be found in [[linear time]] by performing a [[depth -first search]] of the graph, orienting all edges in the depth -first search tree away from the tree root, and orienting all the remaining edges (which must necessarily connect an ancestor and a descendant in the depth -first search tree) from the descendant to the ancestor.<ref>{{harvtxt|Vishkin|1985}} credits this observation to {{harvtxt|Atallah|1984}}, and {{harvtxt|Balakrishnan|1996}} credits it to {{harvtxt|Roberts|1978}}. But as {{harvtxt|Clark|Holton|1991}} point out, the same algorithm is already included (with the assumption of [[k-vertex-connected graph|2-vertex-connectivity]] rather than 2-edge-connectivity) in the seminal earlier work of {{harvtxt|Hopcroft|Tarjan|1973}} on depth -first search.</ref> Although this algorithm is not suitable for [[parallel computer]]s, due to the difficulty of performing depth -first search on them, alternative algorithms are available that solve the problem efficiently in the parallel model.<ref>{{harvtxt|Vishkin|1985}}.</ref> Parallel algorithms are also known for finding strongly connected orientations of mixed graphs.<ref>{{harvtxt|Soroker|1988}}.</ref>

==Applications==

Robbins originally motivated his work by an application to the design of one-way streets in cities. Another application arises in [[structural rigidity]], in the theory of [[grid bracing]]. This theory concerns the problem of making a square grid, constructed from rigid rods attached at flexible joints, rigid by adding more rods or wires as [[cross bracing]] on the diagonals of the grid. A set of added rods makes the grid rigid if an associated undirected graph is connected, and is doubly braced (remaining rigid if any edge is removed) if in addition it is bridgeless. Analogously, a set of added wires (which can bend to reduce the distance between the points they connect, but cannot expand) makes the grid rigid if an associated directed graph is strongly connected.{{sfnp|Baglivo|Graver|1983}} Therefore, reinterpreting Robbins' theorem for this application, the doubly braced structures are exactly the structures whose rods can be replaced by wires while remaining rigid.

==Notes==

Line 31 ⟶ 35:

| title = Parallel strong orientation of an undirected graph

| volume = 18

| year = 1984| url = https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1361&context=cstech }}.

| year = 1984}}.

*{{citation

| last1 = Baglivo | first1 = Jenny A. | author1-link = Jenny Baglivo

| last2 = Graver | first2 = Jack E.

| contribution = 3.10 Bracing structures

| isbn = 9780521297844

| pages = 76–87

| publisher = Cambridge University Press | ___location = Cambridge, UK

| series = Cambridge Urban and Architectural Studies

| title = Incidence and Symmetry in Design and Architecture

| title-link = Incidence and Symmetry in Design and Architecture

| year = 1983}}

*{{citation

| last = Balakrishnan | first = V. K.

| contribution = 4.6 Strong Orientation of Graphs

| isbn = 978-0-486-69115-2

| ___location = Mineola, NY

| mr = 1402469

Line 41 ⟶ 56:

| publisher = Dover Publications Inc.

| title = Introductory Discrete Mathematics

| url = httphttps://books.google.com/books?id=pOBXUoVZ9EEC&pg=PA135

| year = 1996}}.

*{{citation

Line 53 ⟶ 68:

| title = Robbins's theorem for mixed multigraphs

| volume = 87

| year = 1980}}.| jstor = 2321858

}}.

*{{citation

| last1 = Clark | first1 = John

| last2 = Holton | first2 = Derek Allan

| contribution = 7.4 Traffic Flow

| isbn = 978-981-02-0489-1

| ___location = Teaneck, NJ

| mr = 1119781

| pages = 254–260

| publisher = World Scientific Publishing Co. Inc.

| title = A first look at graph theory

| url = https://books.google.com/books?id=vLRNRebXuKYC&pg=PA254

| year = 19841991}}.

*{{citation

| last1 = Gross | first1 = Jonathan L.

| last2 = Yellen | first2 = Jay

| contribution = Characterization of strongly orientable graphs

| edition = 2nd

| isbn = 978-1-58488-505-4

| ___location = Boca Raton, FL

| mr = 2181153

| pages = 498–499

| publisher = Chapman & Hall/CRC

| series = Discrete Mathematics and its Applications

| title = Graph Theory and its Applications

| url = https://books.google.com/books?id=unEloQ_sYmkC&pg=PA498

| year = 2006}}.

*{{citation

| last1 = Hopcroft | first1 = John | author1-link = John Hopcroft

Line 63 ⟶ 105:

| title = Algorithm 447: efficient algorithms for graph manipulation

| volume = 16

| year = 1973}}.| s2cid = 14772567 | doi-access = free

}}.

*{{citation

| last = Robbins | first = H. E. | author-link = Herbert Robbins

Line 71 ⟶ 114:

| title = A theorem on graphs, with an application to a problem on traffic control

| volume = 46

| issue = 5 | year = 1939

| doi=10.2307/2303897}}.

*{{citation

Line 82 ⟶ 125:

| series = CBMS-NSF Regional Conference Series in Applied Mathematics

| title = Graph Theory and its Applications to Problems of Society

| url = httphttps://books.google.com/books?id=EYAwztXnzf8C&pg=PA7

| volume = 29

| year = 1978| isbn = 9780898710267 }}.

*{{citation

| last = Soroker | first = Danny