Robbins' theorem

Source: Wikipedia, the free encyclopedia.
This article is about Robbins' theorem in graph theory. For Robin's theorem in number theory, see divisor function.

In

connected and has no bridge
.

Orientable graphs

An ear decomposition of a bridgeless graph. Orienting each ear as a directed path or a directed cycle makes the whole graph strongly connected.

Robbins' characterization of the graphs with strong orientations may be proven using ear decomposition, a tool introduced by Robbins for this task.

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.[1]

Related results

An extension of Robbins' theorem to mixed graphs by Boesch & Tindell (1980) shows that, if G is a graph in which some edges may be directed and others undirected, and G contains a path respecting the edge orientations from every vertex to every other vertex, then any undirected edge of G that is not a bridge may be made directed without changing the connectivity of G. In particular, a bridgeless undirected graph may be made into a strongly connected directed graph by a greedy algorithm that directs edges one at a time while preserving the existence of paths between every pair of vertices; it is impossible for such an algorithm to get stuck in a situation in which no additional orientation decisions can be made.

Algorithms and complexity

A strong orientation of a given bridgeless undirected graph may be found in

parallel computers, due to the difficulty of performing depth-first search on them, alternative algorithms are available that solve the problem efficiently in the parallel model.[3] Parallel algorithms are also known for finding strongly connected orientations of mixed graphs.[4]

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.[5] 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

  1. ^ Gross & Yellen (2006).
  2. ^ Vishkin (1985) credits this observation to Atallah (1984), and Balakrishnan (1996) credits it to Roberts (1978). But as Clark & Holton (1991) point out, the same algorithm is already included (with the assumption of 2-vertex-connectivity rather than 2-edge-connectivity) in the seminal earlier work of Hopcroft & Tarjan (1973) on depth-first search.
  3. ^ Vishkin (1985).
  4. ^ Soroker (1988).
  5. ^ Baglivo & Graver (1983).

References

Retrieved from "https://en.wikipedia.org/w/index.php?title=Robbins%27_theorem&oldid=1136357352"