Zusammenhang von Graphen

Der Grad des Zusammenhangs bzw. die Konnektivität von Graphen bedeutet intuitiv, dass Wege zwischen mindestens zwei Knoten im Graphen bestehen.

Mathematische Definition

Ungerichtete Graphen

Ein ungerichteter Graph GG=(V,E)(V,E) heißt zusammenhängend, falls es zu je zwei beliebigen Knoten vv und ww aus VV einen ungerichteten Weg in GG gibt, mit vv als Startknoten und ww als Endknoten. Falls GG nicht zusammenhängend ist, nennt man GG unzusammenhängend.
Sind A, BA,\, B und XX Teilmengen von VV und ist YY Teilmenge von EE, so nennt man ZZ=(X, Y)(X,\, Y) einen A-B-Trenner in GG, falls für jeden AA-BB-Weg (v1v_{1},...,vkv_{k}) in GG ein ii aus {1,...,kk} oder ein jj aus {1,...,kk-1} existiert, so dass viv_{i} Element von XX oder {vj,vj+1v_{j},v_{j+1}} Element von YY ist. Man sagt dann, dass ZZ die Knotenmengen AA und BB in GG trennt. Statt "(XX,{}) bzw. ({vv},{}) bzw. ({},YY) bzw. ({},{ee}) trennt AA und BB in GG" sagt man auch "XX bzw. vv bzw. YY bzw. ee trennt AA und BB in GG". Allgemeiner sagt man ZZ trennt GG, wenn ZZ in GG zwei Ecken aus VV\XX trennt.
GG heißt k-fach kantenzusammenhängend, wenn es keine maximal kk-1 elementige Kantenmenge in GG gibt, die GG trennt (in Multigraphen kann man Kanten entsprechend ihrer Vielfachheit mehrfach entfernen). Als Kantenzusammenhangszahl eines Graphen GG bezeichnet man das größte kk, sodass GG kk-fach kantenzusammenhängend ist.
GG heißt k-fach knotenzusammenhängend, wenn es keine maximal kk-1-elementigen Knotenmenge in GG gibt, die GG trennt. Statt kk-fach knotenzusammenhängend sagt man auch oft kürzer k-fach zusammenhängend oder k-zusammenhängend. Als Knotenzusammenhangszahl eines Graphen GG bezeichnet man das größte kk, sodass GG kk-zusammenhängend ist.
Ist UU eine Teilmenge von VV mit der Eigenschaft, dass der von UU induzierte Teilgraph GG[UU] von GG kk-zusammenhängend ist und keine Teilmenge WW von VV mit UU/WW existiert, so dass der von WW induzierte Teilgraph GG[WW] von GG kk-zusammenhängend ist, so nennt man G[U] eine k-Zusammenhangskomponente von GG. Eine 1-Zusammenhangskomponente nennt man auch einfach nur Zusammenhangskomponente und eine 2-Zusammenhangskomponente nennt man Block.
Ein Knoten vv heißt Artikulation von GG, wenn er zwei andere Knoten xx und yy der gleichen Zusammenhangskomponente in GG trennt. Eine Kante ee heißt Brücke von GG, wenn sie ihre beiden inzidenten Knoten trennt.
Man bezeichnet den Graphen, der
  1. als Knotenmenge die Blöcke und Artikulationen von GG enthält,
  2. eine Artikulation aa mit einem Block BB verbindet, falls aa in GG zu BB gehört und
  3. sonst keine weiteren Kanten besitzt
als Blockgraph von GG.

Gerichtete Graphen

Ein gerichteter Graph GG=(V,E)(V,E) heißt zusammenhängend von einem Knoten vv aus, falls es zu jedem Knoten ww aus VV einen gerichteten Weg in GG gibt, mit vv als Startknoten und ww als Endknoten. GG heißt stark zusammenhängend, falls GG von jedem Knoten vv aus VV zusammenhängend ist.
Ein gerichteter Graph heißt zusammenhängend, falls der zugehörige ungerichtete Graph (also der Graph, der entsteht, wenn man jede gerichtete Kante durch eine ungerichtete Kante ersetzt) zusammenhängend ist.
Ein induzierter Teilgraph KK=(VK,EK)(V_{K},E_{K}) von GG heißt starke Zusammenhangskomponente von GG, falls KK stark zusammenhängend ist und kein stark zusammenhängender induzierter Teilgraph von GG exisitiert, der KK echt enthält.
Bemerkung: Es gibt genau dann einen Weg mit vv als Startknoten und ww als Endknoten, wenn es einen Pfad mit vv als Startknoten und ww als Endknoten gibt. In obigen Definitionen kann man Weg also auch durch Pfad ersetzen.

Wichtige Aussagen und Sätze

Relativ leicht zeigt man folgende Aussagen:
  1. Ein ungerichteter Graph ist genau dann zusammenhängend, wenn er einen spannenden Baum enthält.
  2. Ein ungerichteter zusammenhängender Graph ist genau dann 2-zusammenhängend, wenn er keine Artikulation besitzt.
  3. Die Knotenzusammenhangszahl ist höchstens so groß wie Kantenzusammenhangszahl und die Kantenzusammenhangszahl ist höchstens so groß wie der Minimalgrad.
  4. Der Blockgraph GBG_{B} eines Graphen GG ist ein Wald. GBG_{B} ist genau dann Baum (also zusammenhängend), wenn GG zusammenhängend ist.
Ist GG=(V,E)(V,E) ein ungerichteter Graph und sind AA und BB Teilmengen von VV, so ist die kleinste Mächtigkeit einer AA von BB trennenden Knotenmenge gleich der größten Mächtigkeit einer Menge disjunkter AA-BB-Wege in GG. Dieser Satz von Menger (1927) ist eine Verallgemeinerung des Satzes von König (1916), wonach in bipartiten Graphen die Paarungszahl der Knotenüberdeckungszahl entspricht. Man folgert aus ihm leicht den Fächersatz:
Ist BB eine Teilmenge von VV und aa Element von VV\BB, so ist die kleinste Mächtigkeit einer aa von BB in GG trennenden Teilmenge XX von VV\aa gleich der größten Mächtigkeit eines aa-BB-Fächers. Man zeigt dies, indem man AA:=N(a)N(a) setzt (d.h. AA ist die Menge der Nachbarn von aa) und den Satz von Mader anwendet.
Ganz ähnlich folgert man: Sind aa und bb zwei verschiedene Knoten von GG, so gilt:
  1. Sind aa und bb nicht benachbart, so ist die kleinste Mächtigkeit einer aa von bb trennenden Teilmenge von VV\{a, ba,\, b} gleich der größten Mächtigkeit einer Menge disjunkter aa-bb-Wege in GG.
  2. Die kleinste Mächtigkeit einer aa von bb trennenden Teilmenge YY von EE ist gleich der größten Mächtigkeit einer Menge kantendisjunkter aa-bb-Wege in GG.
Daraus lässt sich nun die globale Version des Satzes von Menger ableiten:
  1. GG ist genau dann kk-zusammenhängend, wenn GG zwischen je zwei Ecken kk disjunkte Wege enthält.
  2. GG ist genau dann kk-fach kantenzusammenhängend, wenn GG zwischen je zwei Ecken kk kantendisjunkte Wege enthält.

Wichtige Algorithmen

Mittels Tiefensuche lässt sich leicht ein linearer Algorithmus implementieren, der die Zusammenhangskomponenten eines Graphen berechnet und so einen einfachen Test impliziert, ob der Graph zusammenhängend ist. Der Test, ob ein gerichteter Graph von einem Knoten vv aus zusammenhängend ist, funktioniert analog. Von Tarjan (1972) stammt ein linearer Algorithmus, der ebenfalls auf Tiefensuche basiert und in gerichteten Graphen die starken Zusammenhangskomponenten und leicht modifiziert in ungerichteten Graphen die Blöcke und Artikulationen berechnet.
Zur Berechnung von Knoten- und Kantenzusammenhangszahl gibt es polynomielle Algorithmen. Dazu kann man beispielsweise Flussalgorithmen verwenden. Allerdings gibt es auch effizientere Algorithmen.
 
 

Alle Pädagogen sind sich darin einig: man muß vor allem tüchtig Mathematik treiben, weil ihre Kenntnis fürs Leben größten direkten Nutzen gewährt.

Felix Klein

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Zusammenhang von Graphen aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Diskrete Mathematik