Der Satz von Robbins (nach Herbert Robbins) ist ein Satz aus der Graphentheorie der einen Zusammenhang zwischen dem Kantenzusammenhang eines ungerichteten Graphen und der Möglichkeit die Kanten so zu orientieren, dass ein stark zusammenhängender gerichteter Graph entsteht herstellt.

Der Satz besagt, dass die Kanten eines zusammenhängender ungerichteten Graphen genau dann so orientiert werden können, dass der entstehende gerichtete Graph stark zusammenhängend ist wenn der ursprüngliche Graph 2-fach kantenzusammenhängend ist (keine Brücken enthält).

Formulierung des Satzes

Algorithmus

Der folgende Algorithmus berechnet für einen 2-fach kantenzusammenhängen Graphen ${\displaystyle G=(V,E)}$ eine Orientierung ${\displaystyle H}$ von ${\displaystyle G}$ sodass ${\displaystyle H}$ stark zusammenhängend ist. Er geht auf die Informatiker John E. Hopcroft und Robert Tarjan zurück.

Der Algorithmus geht in zwei Schritten vor: Zuerst werden die Kanten eines Gerüstes orientiert, das über Tiefensuche bestimmt wird, anschließend werden die restlichen Kanten orientiert.

Es sei

• ${\displaystyle M}$ die Menge der markierten Knoten,
• ${\displaystyle NM}$ die Menge der nicht markierten Knoten,
• ${\displaystyle m\colon V\to \mathbb {N} }$ die Markierung der Knoten,
• ${\displaystyle OM}$ die Menge der Bögen, die durch die Orientierung der Kanten von ${\displaystyle G}$ entstanden sind.

1. Wähle einen beliebigen Knoten ${\displaystyle x\in V}$ von ${\displaystyle G}$ aus, der markiert wird:

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

2. Suche jetzt einen Knoten ${\displaystyle y}$ von ${\displaystyle M}$, der eine maximale Markierung ${\displaystyle m(y)}$ und gleichfalls adjazent zu einem Knoten ${\displaystyle z}$ aus ${\displaystyle NM}$ ist. Markiere jetzt ${\displaystyle z}$ mit ${\displaystyle m(z)=m(y)+1}$. Orientiere anschließend die Kante ${\displaystyle \{y,z\}}$ von ${\displaystyle y}$ zu ${\displaystyle z}$, so dass der Bogen ${\displaystyle (y,z)}$ entsteht.

Der markierte Knoten ${\displaystyle z}$ wird aus ${\displaystyle NM}$ entfernt und zu ${\displaystyle M}$ hinzugefügt, und der Bogen ${\displaystyle (y,z)}$ wird zu ${\displaystyle OM}$ hinzugefügt:

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

Überprüfe, ob alle Knoten markiert wurden: Gilt ${\displaystyle M\neq V}$, dann wiederhole Schritt 2.

3. Es gilt:

• Alle Knoten wurden markiert: ${\displaystyle M=V}$,
• ein Gerüst von ${\displaystyle G}$ ist orientiert.

Es lässt sich beweisen, dass alle Kanten, die jetzt noch keine Richtung haben, immer zwei Knoten mit unterschiedlicher Markierung verbinden. Jede nicht orientierte Kante ${\displaystyle \{x,y\}}$ mit ${\displaystyle m(x)>m(y)}$ wird nun von ${\displaystyle x}$ nach ${\displaystyle y}$ orientiert, d. h. vom Knoten mit der größeren zum Knoten mit der kleineren Markierung, und zu ${\displaystyle OM}$ hinzugefügt.

Die auf diese Weise konstruierte Orientierung ${\displaystyle H=(V,OM)}$ des Graphen ${\displaystyle G}$ ist stark zusammenhängend.

Literatur

• Frank Bosch, Ralph Tindell: Robbins's theorem for mixed multigraphs. In: American Mathematical Monthly. Band 87, Nr. 9, 1980, S. 716–719, doi:10.2307/2321858. 
• John Hopcroft, Robert Tarjan: Algorithm 447: efficient algorithms for graph manipulation. In: Communications of the ACM. Band 16, Nr. 6, 1973, S. 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. Band 46, 1939, S. 281–283, doi:10.2307/2303897. 

Einzelnachweise

1. 1 2 Boesch und Tindell (1980)
2. ↑ Hopcroft and Tarjan (1973)