Satz von Robbins

Satz aus der Graphentheorie

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

Bearbeiten
Ein zusammenhängender ungerichteten Graphen hat genau dann eine stark zusammenhängende Orientierung wenn der ursprüngliche Graph 2-fach kantenzusammenhängend ist.

Unter einer Orientierung eines ungerichten Graphen   versteht man einen gerichteter Graph   sodass für jede ungerichte Kante   genau eine der gerichteten Kanten   in   ist.

Multigraphen

Bearbeiten

Der Satz kann auf Multigraphen verallgemeinert werden[1].

Ein zusammenhängender Multigraph hat genau dann eine stark zusammenhängende Orientierung wenn der ursprüngliche Multigraph 2-fach kantenzusammenhängend ist.

Gemischte Graphen

Bearbeiten

Boesch und Tindell haben den Satz von Robbins auf gemischte Graphen, Graphen die sowohl gerichtete als auch ungerichtete Kanten enthalten[1].

Ein solcher Graph ist zusammenhängend, wenn es für jedes Paar von Knoten   einen Pfad von   nach   gibt, wobei gerichtete Kanten nur in der gegebenen Richtung verwendet werden durften.

Ein zusammenhängender gemischter Multigraph hat genau dann eine stark zusammenhängende Orientierung, wenn er 2-fach kantenzusammenhängend ist.

Algorithmus

Bearbeiten

Der folgende Algorithmus berechnet für einen 2-fach kantenzusammenhängen Graphen   eine Orientierung   von   sodass   stark zusammenhängend ist. Er geht auf die Informatiker John E. Hopcroft und Robert Tarjan[2] 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

  •   die Menge der markierten Knoten,
  •   die Menge der nicht markierten Knoten,
  •   die Markierung der Knoten,
  •   die Menge der Bögen, die durch die Orientierung der Kanten von   entstanden sind.

1. Wähle einen beliebigen Knoten   von   aus, der markiert wird:

Setze  

2. Suche jetzt einen Knoten   von  , der eine maximale Markierung   und gleichfalls adjazent zu einem Knoten   aus   ist. Markiere jetzt   mit  . Orientiere anschließend die Kante   von   zu  , so dass der Bogen   entsteht.

Der markierte Knoten   wird aus   entfernt und zu   hinzugefügt, und der Bogen   wird zu   hinzugefügt:

 

Überprüfe, ob alle Knoten markiert wurden: Gilt  , dann wiederhole Schritt 2.

3. Es gilt:

  • Alle Knoten wurden markiert:  ,
  • ein Gerüst von   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   mit   wird nun von   nach   orientiert, d. h. vom Knoten mit der größeren zum Knoten mit der kleineren Markierung, und zu   hinzugefügt.

Die auf diese Weise konstruierte Orientierung   des Graphen   ist stark zusammenhängend.

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. a b Boesch und Tindell (1980)
  2. Hopcroft and Tarjan (1973)