Robbins' theorem

The set of Robbins (by Herbert Robbins ) is a set of the graph theory of a connection between the edge connection of an undirected graph to orient and the possibility of the edges so that a strongly connected directed graph prepared arises.

The theorem says that the edges of a connected undirected graph can be oriented in such a way that the resulting directed graph is strongly connected if the original graph is 2-fold edge-connected ( contains no bridges ).

Formulation of the sentence

Graph

A connected undirected graph has a strongly connected orientation if and only if the original graph is 2-fold edge-connected.

Under an orientation of an undirected graph is defined as a directed graph such that for each un-eights edge exactly one of the directed edges in is. ${\displaystyle G=(V,E)}$ ${\displaystyle O=(V,E')}$ ${\displaystyle \{v,u\}\in E}$ ${\displaystyle (v,u),(u,v)}$ ${\displaystyle E'}$

Multigraphs

The theorem can be generalized to multigraphs .

A connected multigraph has a strongly connected orientation if and only if the original multigraph is 2-fold edge-connected.

Mixed graph

Boesch and Tindell found Robbins' theorem on mixed graphs, graphs that contain both directed and undirected edges.

Such a graph is connected if for every pair of nodes there is a path from to where directed edges could only be used in the given direction. ${\displaystyle u,v}$ ${\displaystyle u}$ ${\displaystyle v}$

A connected mixed multigraph has a strongly connected orientation if and only if it is 2-fold edge-connected.

algorithm

The following algorithm calculates for a 2-fold edge-connected graph an orientation of so that it is strongly connected. It goes back to the computer scientists John E. Hopcroft and Robert Tarjan . ${\displaystyle G=(V,E)}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$

The algorithm proceeds in two steps: First, the edges of a framework are oriented, which is determined using depth-first search , then the remaining edges are oriented.

Be it

• ${\displaystyle M}$the set of marked nodes ,
• ${\displaystyle NM}$ the set of unmarked nodes,
• ${\displaystyle m\colon V\to \mathbb {N} }$ the marking of the knots,
• ${\displaystyle OM}$the amount of arcs created by orienting the edges of . ${\displaystyle G}$

1. Choose an arbitrary node of from, which is marked: ${\displaystyle x\in V}$ ${\displaystyle G}$

Set ${\displaystyle m(x)=1;M=\{x\};NM=V\setminus \{x\};OM=\emptyset }$

2. Now look for a node of , which is a maximal marking and also adjacent to a node from . Now mark with . Then orient the edge of to so that the arch is created. ${\displaystyle y}$ ${\displaystyle M}$ ${\displaystyle m(y)}$ ${\displaystyle z}$ ${\displaystyle NM}$ ${\displaystyle z}$ ${\displaystyle m(z)=m(y)+1}$ ${\displaystyle \{y,z\}}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle (y,z)}$

The highlighted node is removed from and added to, and the arc is added to: ${\displaystyle z}$ ${\displaystyle NM}$ ${\displaystyle M}$ ${\displaystyle (y,z)}$ ${\displaystyle OM}$

${\displaystyle M=M\cup \{z\};NM=NM\setminus \{z\};OM=OM\cup \{(y,z)\}}$

Check that all nodes have been marked: Applies , then repeat step 2. ${\displaystyle M\neq V}$

3. The following applies:

• All nodes were marked: , ${\displaystyle M=V}$
• a framework of is oriented. ${\displaystyle G}$

It can be proven that all edges that now have no direction always connect two nodes with different markings. Every unoriented edge with is now oriented from to , i.e. H. from the node with the larger to the node with the smaller mark, and added to. ${\displaystyle \{x,y\}}$ ${\displaystyle m(x)>m(y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle OM}$

The orientation of the graph constructed in this way is strongly connected. ${\displaystyle H=(V,OM)}$ ${\displaystyle G}$

literature

• Frank Bosch, Ralph Tindell: Robbins's theorem for mixed multigraphs . In: American Mathematical Monthly . tape 87 , no. 9 , 1980, pp. 716-719 , doi : 10.2307 / 2321858 .
• John Hopcroft , Robert Tarjan : Algorithm 447: efficient algorithms for graph manipulation . In: Communications of the ACM . tape 16 , no. 6 , 1973, p. 372-378 , doi : 10.1145 / 362248.362272 .
• Herbert Robbins : A theorem on graphs, with an application to a problem on traffic control . In: American Mathematical Monthly . tape 46 , 1939, pp. 281-283 , doi : 10.2307 / 2303897 .

Individual evidence

1. ↑ ^{a b} Boesch and Tindell (1980)
2. ↑ Hopcroft and Tarjan (1973)