www.wikidata.de-de.nina.az

k Zusammenhang Der eines Graphen ist ein wichtiger Begriff in der Graphentheorie und eine Verallgemeinerung des Zusammen

k-Zusammenhang

Der k-Zusammenhang eines Graphen ist ein wichtiger Begriff in der Graphentheorie und eine Verallgemeinerung des Zusammenhangs. Anschaulich ist der k-Zusammenhang ein Maß dafür, wie schwierig es ist, einen Graphen durch Löschen von Knoten in zwei Komponenten zu zerlegen. Ist der k-Zusammenhang groß, so müssen viele Knoten gelöscht werden.

Definition Bearbeiten

Ungerichtete Graphen Bearbeiten

Ein ungerichteter Graph (welcher auch ein Multigraph sein kann) heißt k-fach knotenzusammenhängend (oder auch einfach k-fach zusammenhängend oder k-zusammenhängend), wenn es keinen Trenner in mit einer maximal -elementigen Knotenmenge und leerer Kantenmenge gibt. Äquivalent dazu ist, dass für alle Knotenmengen mit Mächtigkeit der von induzierte Teilgraph zusammenhängend ist.

Ist eine Teilmenge der Knotenmenge mit der Eigenschaft, dass der von induzierte Teilgraph -zusammenhängend ist und für jede Knotenmenge nicht -zusammenhängend ist, so nennt man eine k-Zusammenhangskomponente von . Eine 2-Zusammenhangskomponente nennt man auch einen Block.

Als Knotenzusammenhangszahl (oft kurz Zusammenhangszahl oder Zusammenhang genannt) eines Graphen bezeichnet man das größte , sodass -zusammenhängend ist. Eine dazu äquivalente Definition ist, dass die Knotenzusammenhangszahl die kleinste Mächtigkeit eines Trenners von mit leerer Kantenmenge ist. Graphen, die k-zusammenhängend sind, haben Zusammenhangszahlen , die größer gleich sind: .

Gerichtete Graphen Bearbeiten

Ein gerichteter Graph (welcher auch Mehrfachkanten enthalten kann) heißt k-fach stark zusammenhängend, wenn für jede Knotenmenge der Mächtigkeit der von induzierte Teilgraph stark zusammenhängend ist.

Das größte , so dass -fach stark zusammenhängend ist, wird starke Zusammenhangszahl genannt und mit bezeichnet.

Beispiel Bearbeiten

K-facher Zusammenhang Bearbeiten

Das ist das Haus vom Nikolaus

Betrachte als Beispiel das rechts dargestellte Haus vom Nikolaus. Es ist 2-zusammenhängend, da keine Trenner existieren, die nur aus einem Knoten bestehen. Äquivalent dazu ist, dass keine Artikulation existiert. Betrachtet man aber nun z. B. die Knoten 3 und 4, so trennen diese das Haus in die Knotenmengen 5 sowie 1 und 2, da jeder Weg von 5 nach 1 oder 2 durch einen der Knoten 3 oder 4 gehen muss. Das Haus ist also einfach und zweifach knotenzusammenhängend und seine Knotenzusammenhangszahl ist .

K-fach starker Zusammenhang Bearbeiten

Der im Beispiel behandelte Digraph

Betrachte als Beispielgraph den rechts dargestellten Turniergraph. Der Graph ist stark zusammenhängend, also auf jeden Fall einfach stark zusammenhängend. Beginnt man mit dem Löschen von einelementigen Knotenmengen, so wird der starke Zusammenhang jedoch bald zerstört. Entfernt man z. B. den Knoten 3, so ist der Knoten 2 von Knoten 4 aus nicht mehr erreichbar. Somit ist der Digraph einfach stark zusammenhängend und .

Eigenschaften Bearbeiten

  • Jeder -zusammenhängende Graph ist auch -zusammenhängend (da es keine -elementige Knotenmenge gibt, die trennt, gibt es natürlich auch keine -elementige).
  • Ein einfacher Graph ist genau dann 2-zusammenhängend, wenn er keine Artikulation besitzt.
  • Eine 1-Zusammenhangskomponente ist genau die klassische Zusammenhangskomponente.
  • Ist , so gilt , wobei die Kantenzusammenhangszahl und der Minimalgrad des Graphen ist. Hoher Zusammenhang setzt also hohen Minimalgrad voraus. Der Umkehrschluss gilt jedoch nicht.
  • ist genau dann -zusammenhängend, wenn zwischen je zwei Knoten disjunkte Wege enthält. Diese Aussage ist auch als die globale Version des Satzes von Menger bekannt.

Algorithmen Bearbeiten

Bestimmung der Knotenzusammenhangszahl Bearbeiten

Zur Berechnung der Knotenzusammenhangszahl gibt es polynomielle Algorithmen. Dazu kann man beispielsweise Flussalgorithmen verwenden. Hierfür berechnet man für alle Knotenpaare einen maximalen --Fluss. Der kleinste Wert, den der Fluss annimmt, ist dann nach dem Satz von Menger die Knotenzusammenhangszahl. Ist also der benötigte Aufwand, einen --Fluss in einem Graphen mit n Knoten und m Kanten zu bestimmen, so liefert dieser naive Ansatz immerhin einen Aufwand von . Allerdings gibt es auch effizientere Algorithmen.

Ein sehr guter, aber komplizierter Algorithmus zur Berechnung des Kantenzusammenhangs eines gerichteten (und damit auch ungerichteten) Graphen mit rationalen Gewichten wurde von H. Gabow entwickelt (basierend auf der Matroid-Theorie, also einer Menge von Teilbäumen).

Ein leichter und auch für reelle Gewichte geeigneter Algorithmus existiert, entdeckt von Stoer/Wagner und zeitgleich Nagamotchi/Ibaraki. Dieser funktioniert mittels Knotenkontraktion und nur für ungerichtete Graphen.

Ein auf Flussalgorithmen basierender Algorithmus für gerichtete Graphen wurde von Hao/Orlin vorgestellt.

Test auf k-Zusammenhang Bearbeiten

Ist man nicht an der Knotenzusammenhangszahl interessiert, sondern will man nur wissen, ob ein Graph k-zusammenhängend ist für vorgegebenes k, so gibt es schnelle Algorithmen. So kann der 2-Zusammenhang in linearer Zeit bestimmt werden. Für ungerichtete Graphen gibt es lineare Algorithmen, die einen 3-Zusammenhang überprüfen. Für 4-Zusammenhang in ungerichteten Graphen existieren Algorithmen mit Aufwand

Verwandte Begriffsbildungen Bearbeiten

Der Kantenzusammenhang ist ein zum k-Zusammenhang ähnlicher Begriff, bloß dass nur Trenner mit leerer Knotenmenge und einer beliebigen Kantenmenge betrachtet werden. Der Kantenzusammenhang gibt also ein Maß dafür an, wie viele Kanten aus einem Graphen entfernt werden müssen, so dass dieser in verschiedene Komponenten zerfällt. Einen zum Kantenzusammenhang analogen Begriff für gerichtete Graphen bildet der Bogenzusammenhang, welcher anstelle von ungerichteten Kanten gerichtete Kanten betrachtet.

Anzahl einfacher nicht-isomorpher unbenannter Graphen Bearbeiten

Anzahl der verschiedenen nicht-isomorphen einfachen unbenannten -zusammenhängenden Graphen mit Knoten für von 1 bis 9, inklusive der Referenz OEIS (einfache Graphen umfassen sowohl zusammenhängende, wie auch nicht zusammenhängende):

\ 1 2 3 4 5 6 7 8 9 OEIS
einfach 1 2 4 11 34 156 1044 12346 274668 A000088
1 1 1 2 6 21 112 853 11117 261080 A001349
2 0 1 1 3 10 56 468 7123 194066 A002218
3 0 0 1 1 3 17 136 2388 80890 A006290
4 0 0 0 1 1 4 25 384 14480 A086216
5 0 0 0 0 1 1 4 39 1051 A086217
6 0 0 0 0 0 1 1 5 59
7 0 0 0 0 0 0 1 1 5

Anzahl der verschiedenen nicht-isomorphen einfachen unbenannten Graphen mit Knoten und der Knotenzusammenhangszahl :

\ 1 2 3 4 5 6 7 8 9 OEIS
0 0 1 2 5 13 44 191 1229 13588
1 1 0 1 3 11 56 385 3994 67014 A052442
2 0 1 0 2 7 39 332 4735 113176 A052443
3 0 0 1 0 2 13 111 2004 66410 A052444
4 0 0 0 1 0 3 21 345 13429 A052445
5 0 0 0 0 1 0 3 34 992
6 0 0 0 0 0 1 0 4 54

Literatur Bearbeiten

  • Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 S.).
  • Lutz Volkmann: Fundamente der Graphentheorie. Springer, Wien 1996, ISBN 3-211-82774-9 („Graphen an allen Ecken und Kanten“ [PDF; 3,7 MB]).
  • Alexander Schrijver: Combinatorial optimization. polyhedra and efficiency. Springer, Berlin 2003, ISBN 3-540-44389-4 (1881 S., 3 Bände).

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der k Zusammenhang eines Graphen ist ein wichtiger Begriff in der Graphentheorie und eine Verallgemeinerung des Zusammenhangs Anschaulich ist der k Zusammenhang ein Mass dafur wie schwierig es ist einen Graphen durch Loschen von Knoten in zwei Komponenten zu zerlegen Ist der k Zusammenhang gross so mussen viele Knoten geloscht werden Inhaltsverzeichnis 1 Definition 1 1 Ungerichtete Graphen 1 2 Gerichtete Graphen 2 Beispiel 2 1 K facher Zusammenhang 2 2 K fach starker Zusammenhang 3 Eigenschaften 4 Algorithmen 4 1 Bestimmung der Knotenzusammenhangszahl 4 2 Test auf k Zusammenhang 5 Verwandte Begriffsbildungen 6 Anzahl einfacher nicht isomorpher unbenannter Graphen 7 Literatur 8 WeblinksDefinition BearbeitenUngerichtete Graphen Bearbeiten Ein ungerichteter Graph G V E displaystyle G V E nbsp welcher auch ein Multigraph sein kann heisst k fach knotenzusammenhangend oder auch einfach k fach zusammenhangend oder k zusammenhangend wenn es keinen Trenner T X Y displaystyle T X Y nbsp in G displaystyle G nbsp mit einer maximal k 1 displaystyle k 1 nbsp elementigen Knotenmenge X displaystyle X nbsp und leerer Kantenmenge Y displaystyle Y emptyset nbsp gibt Aquivalent dazu ist dass fur alle Knotenmengen K displaystyle K nbsp mit Machtigkeit k 1 displaystyle k 1 nbsp der von V K displaystyle V backslash K nbsp induzierte Teilgraph zusammenhangend ist Ist U displaystyle U nbsp eine Teilmenge der Knotenmenge V displaystyle V nbsp mit der Eigenschaft dass der von U displaystyle U nbsp induzierte Teilgraph G U displaystyle G U nbsp k displaystyle k nbsp zusammenhangend ist und G W displaystyle G W nbsp fur jede Knotenmenge W U W U displaystyle W supset U W neq U nbsp nicht k displaystyle k nbsp zusammenhangend ist so nennt man G U displaystyle G U nbsp eine k Zusammenhangskomponente von G displaystyle G nbsp Eine 2 Zusammenhangskomponente nennt man auch einen Block Als Knotenzusammenhangszahl k G displaystyle kappa G nbsp oft kurz Zusammenhangszahl oder Zusammenhang genannt eines Graphen G displaystyle G nbsp bezeichnet man das grosste k displaystyle k nbsp sodass G displaystyle G nbsp k displaystyle k nbsp zusammenhangend ist Eine dazu aquivalente Definition ist dass die Knotenzusammenhangszahl die kleinste Machtigkeit eines Trenners von G displaystyle G nbsp mit leerer Kantenmenge ist Graphen die k zusammenhangend sind haben Zusammenhangszahlen k G displaystyle kappa G nbsp die grosser gleich k displaystyle k nbsp sind k G k displaystyle kappa G geq k nbsp Gerichtete Graphen Bearbeiten Ein gerichteter Graph D V A displaystyle D V A nbsp welcher auch Mehrfachkanten enthalten kann heisst k fach stark zusammenhangend wenn fur jede Knotenmenge U displaystyle U nbsp der Machtigkeit k 1 displaystyle k 1 nbsp der von V U displaystyle V backslash U nbsp induzierte Teilgraph G V U displaystyle G left V backslash U right nbsp stark zusammenhangend ist Das grosste k displaystyle k nbsp so dass D displaystyle D nbsp k displaystyle k nbsp fach stark zusammenhangend ist wird starke Zusammenhangszahl genannt und mit s D displaystyle sigma D nbsp bezeichnet Beispiel BearbeitenK facher Zusammenhang Bearbeiten nbsp Das ist das Haus vom NikolausBetrachte als Beispiel das rechts dargestellte Haus vom Nikolaus Es ist 2 zusammenhangend da keine Trenner existieren die nur aus einem Knoten bestehen Aquivalent dazu ist dass keine Artikulation existiert Betrachtet man aber nun z B die Knoten 3 und 4 so trennen diese das Haus in die Knotenmengen 5 sowie 1 und 2 da jeder Weg von 5 nach 1 oder 2 durch einen der Knoten 3 oder 4 gehen muss Das Haus ist also einfach und zweifach knotenzusammenhangend und seine Knotenzusammenhangszahl ist k G 2 displaystyle kappa G 2 nbsp K fach starker Zusammenhang Bearbeiten nbsp Der im Beispiel behandelte DigraphBetrachte als Beispielgraph den rechts dargestellten Turniergraph Der Graph ist stark zusammenhangend also auf jeden Fall einfach stark zusammenhangend Beginnt man mit dem Loschen von einelementigen Knotenmengen so wird der starke Zusammenhang jedoch bald zerstort Entfernt man z B den Knoten 3 so ist der Knoten 2 von Knoten 4 aus nicht mehr erreichbar Somit ist der Digraph einfach stark zusammenhangend und s D 1 displaystyle sigma D 1 nbsp Eigenschaften BearbeitenJeder k displaystyle k nbsp zusammenhangende Graph ist auch k 1 displaystyle k 1 nbsp zusammenhangend da es keine k 1 displaystyle k 1 nbsp elementige Knotenmenge gibt die G displaystyle G nbsp trennt gibt es naturlich auch keine k 2 displaystyle k 2 nbsp elementige Ein einfacher Graph ist genau dann 2 zusammenhangend wenn er keine Artikulation besitzt Eine 1 Zusammenhangskomponente ist genau die klassische Zusammenhangskomponente Ist G 2 displaystyle G geq 2 nbsp so gilt d G l G k G displaystyle delta G geq lambda G geq kappa G nbsp wobei l G displaystyle lambda G nbsp die Kantenzusammenhangszahl und d G displaystyle delta G nbsp der Minimalgrad des Graphen G displaystyle G nbsp ist Hoher Zusammenhang setzt also hohen Minimalgrad voraus Der Umkehrschluss gilt jedoch nicht G displaystyle G nbsp ist genau dann k displaystyle k nbsp zusammenhangend wenn G displaystyle G nbsp zwischen je zwei Knoten k displaystyle k nbsp disjunkte Wege enthalt Diese Aussage ist auch als die globale Version des Satzes von Menger bekannt Algorithmen BearbeitenBestimmung der Knotenzusammenhangszahl Bearbeiten Zur Berechnung der Knotenzusammenhangszahl gibt es polynomielle Algorithmen Dazu kann man beispielsweise Flussalgorithmen verwenden Hierfur berechnet man fur alle Knotenpaare s t displaystyle s t nbsp einen maximalen s displaystyle s nbsp t displaystyle t nbsp Fluss Der kleinste Wert den der Fluss annimmt ist dann nach dem Satz von Menger die Knotenzusammenhangszahl Ist also F n m displaystyle F n m nbsp der benotigte Aufwand einen s displaystyle s nbsp t displaystyle t nbsp Fluss in einem Graphen mit n Knoten und m Kanten zu bestimmen so liefert dieser naive Ansatz immerhin einen Aufwand von O n 2 F n m displaystyle mathcal O n 2 F n m nbsp Allerdings gibt es auch effizientere Algorithmen Ein sehr guter aber komplizierter Algorithmus zur Berechnung des Kantenzusammenhangs eines gerichteten und damit auch ungerichteten Graphen mit rationalen Gewichten wurde von H Gabow entwickelt basierend auf der Matroid Theorie also einer Menge von Teilbaumen Ein leichter und auch fur reelle Gewichte geeigneter Algorithmus existiert entdeckt von Stoer Wagner und zeitgleich Nagamotchi Ibaraki Dieser funktioniert mittels Knotenkontraktion und nur fur ungerichtete Graphen Ein auf Flussalgorithmen basierender Algorithmus fur gerichtete Graphen wurde von Hao Orlin vorgestellt Test auf k Zusammenhang Bearbeiten Ist man nicht an der Knotenzusammenhangszahl interessiert sondern will man nur wissen ob ein Graph k zusammenhangend ist fur vorgegebenes k so gibt es schnelle Algorithmen So kann der 2 Zusammenhang in linearer Zeit bestimmt werden Fur ungerichtete Graphen gibt es lineare Algorithmen die einen 3 Zusammenhang uberprufen Fur 4 Zusammenhang in ungerichteten Graphen existieren Algorithmen mit Aufwand O n 2 displaystyle mathcal O n 2 nbsp Verwandte Begriffsbildungen BearbeitenDer Kantenzusammenhang ist ein zum k Zusammenhang ahnlicher Begriff bloss dass nur Trenner mit leerer Knotenmenge und einer beliebigen Kantenmenge betrachtet werden Der Kantenzusammenhang gibt also ein Mass dafur an wie viele Kanten aus einem Graphen entfernt werden mussen so dass dieser in verschiedene Komponenten zerfallt Einen zum Kantenzusammenhang analogen Begriff fur gerichtete Graphen bildet der Bogenzusammenhang welcher anstelle von ungerichteten Kanten gerichtete Kanten betrachtet Anzahl einfacher nicht isomorpher unbenannter Graphen BearbeitenAnzahl der verschiedenen nicht isomorphen einfachen unbenannten k displaystyle k nbsp zusammenhangenden Graphen mit n displaystyle n nbsp Knoten fur n displaystyle n nbsp von 1 bis 9 inklusive der Referenz OEIS einfache Graphen umfassen sowohl zusammenhangende wie auch nicht zusammenhangende k displaystyle k nbsp n displaystyle n nbsp 1 2 3 4 5 6 7 8 9 OEISeinfach 1 2 4 11 34 156 1044 12346 274668 A0000881 1 1 2 6 21 112 853 11117 261080 A0013492 0 1 1 3 10 56 468 7123 194066 A0022183 0 0 1 1 3 17 136 2388 80890 A0062904 0 0 0 1 1 4 25 384 14480 A0862165 0 0 0 0 1 1 4 39 1051 A0862176 0 0 0 0 0 1 1 5 597 0 0 0 0 0 0 1 1 5Anzahl der verschiedenen nicht isomorphen einfachen unbenannten Graphen mit n displaystyle n nbsp Knoten und der Knotenzusammenhangszahl k displaystyle kappa nbsp k displaystyle kappa nbsp n displaystyle n nbsp 1 2 3 4 5 6 7 8 9 OEIS0 0 1 2 5 13 44 191 1229 135881 1 0 1 3 11 56 385 3994 67014 A0524422 0 1 0 2 7 39 332 4735 113176 A0524433 0 0 1 0 2 13 111 2004 66410 A0524444 0 0 0 1 0 3 21 345 13429 A0524455 0 0 0 0 1 0 3 34 9926 0 0 0 0 0 1 0 4 54Literatur BearbeitenReinhard Diestel Graphentheorie Springer Berlin 2010 ISBN 978 3 642 14911 5 354 S Lutz Volkmann Fundamente der Graphentheorie Springer Wien 1996 ISBN 3 211 82774 9 Graphen an allen Ecken und Kanten PDF 3 7 MB Alexander Schrijver Combinatorial optimization polyhedra and efficiency Springer Berlin 2003 ISBN 3 540 44389 4 1881 S 3 Bande Weblinks BearbeitenWolfram Mathworld k Connected Graph Abgerufen von https de wikipedia org w index php title K Zusammenhang amp oldid 230071692