Zusammenhang von Graphen

Stichpunkte

Allgemein
	[Bearbeiten]
Definitionen
	Ein ungerichteter Graph G=(V
	E) heißt zusammenhängend
	falls es zu je zwei beliebigen Knoten v und w aus V einen ungerichteten Weg in G gibt
	mit v als Startknoten und w als Endknoten
	nennt man G unzusammenhängend
	Falls G nicht zusammenhängend ist
	so nennt man Z=(X
	vk) in G ein i aus {1
	Y) einen A-B-Trenner in G
	...
	k} oder ein j aus {1
	B und X Teilmengen von V und ist Y Teilmenge von E
	Sind A
	vj+1} Element von Y ist
	falls für jeden A-B-Weg (v1
	so dass vi Element von X oder {vj
	...
	...
	k-1} existiert
	dass Z die Knotenmengen A und B in G trennt
	Man sagt dann
	{}) bzw. ({}
	Y) bzw. ({}
	Statt "(X
	{}) bzw. ({v}
	{e}) trennt A und B in G" sagt man auch "X bzw. v bzw
	Y bzw. e trennt A und B in G"
	Allgemeiner sagt man Z trennt G
	wenn Z in G zwei Ecken aus VX trennt
	wenn es keine maximal k-1 elementige Kantenmenge in G gibt
	G heißt k-fach kantenzusammenhängend
	die G trennt (in Multigraphen kann man Kanten entsprechend ihrer Vielfachheit mehrfach entfernen)
	Als Kantenzusammenhangszahl eines Graphen G bezeichnet man das größte k
	sodass G k-fach kantenzusammenhängend ist
	G heißt k-fach knotenzusammenhängend
	die G trennt
	wenn es keine maximal k-1-elementigen Knotenmenge in G gibt
	Statt k-fach knotenzusammenhängend sagt man auch oft kürzer k-fach zusammenhängend oder k-zusammenhängend
	sodass G k-zusammenhängend ist
	Als Knotenzusammenhangszahl eines Graphen G bezeichnet man das größte k
	Ist U eine Teilmenge von V mit der Eigenschaft
	so dass der von W induzierte Teilgraph G[W] von G k-zusammenhängend ist
	dass der von U induzierte Teilgraph G[U] von G k-zusammenhängend ist und keine Teilmenge W von V mit U⊂W existiert
	so nennt man G[U] eine k-Zusammenhangskomponente von G
	Eine 1-Zusammenhangskomponente nennt man auch einfach nur Zusammenhangskomponente und eine 2-Zusammenhangskomponente nennt man Block
	Ein Knoten v heißt Artikulation von G
	wenn er zwei andere Knoten x und y der gleichen Zusammenhangskomponente in G trennt
	wenn sie ihre beiden inzidenten Knoten trennt
	Eine Kante e heißt Brücke von G
	falls a in G zu B gehört und sonst keine weiteren Kanten besitzt als Blockgraph von G
	der als Knotenmenge die Blöcke und Artikulationen von G enthält
	Man bezeichnet den Graphen
	eine Artikulation a mit einem Block B verbindet
	Ein gerichteter Graph G=(V
	mit v als Startknoten und w als Endknoten
	falls es zu jedem Knoten w aus V einen gerichteten Weg in G gibt
	E) heißt zusammenhängend von einem Knoten v aus
	Falls G nicht von v aus zusammenhängend ist
	nennt man G unzusammenhängend von v aus
	G heißt stark zusammenhängend
	falls G von jedem Knoten v aus V zusammenhängend ist
	EK) von G heißt starke Zusammenhangskomponente von G
	Ein induzierter Teilgraph K=(VK
	falls K stark zusammenhängend ist und in G kein Knoten aus VK Vorgänger oder Nachfolger von einem Knoten aus der Differenzmenge VVK ist
	Bemerkung: Es gibt genau dann einen Weg mit v als Startknoten und w als Endknoten
	wenn es einen Pfad mit v als Startknoten und w als Endknoten gibt
	In obigen Definitionen kann man Weg also auch durch Pfad ersetzen. [Bearbeiten]
wichtige Aussagen und Sätze
	wenn er einen spannenden Baum enthält
	Relativ leicht zeigt man folgende Aussagen: Ein ungerichteter Graph ist genau dann zusammenhängend
	wenn er keine Artikulation besitzt
	Ein ungerichteter zusammenhängender Graph ist genau dann 2-zusammenhängend
	Die Knotenzusammenhangszahl ist höchstens so groß wie Kantenzusammenhangszahl und die Kantenzusammenhangszahl ist höchstens so groß wie der Minimalgrad
	Der Blockgraph GB eines Graphen G ist ein Wald
	wenn G zusammenhängend ist. Ist G=(V
	E) ein ungerichteter Graph und sind A und B Teilmengen von V
	so ist die kleinste Mächtigkeit einer A von B trennenden Knotenmenge gleich der größten Mächtigkeit einer Menge disjunkter A-B-Wege in G
	GB ist genau dann Baum (also zusammenhängend)
	wonach in bipartiten Graphen die Paarungszahl der Knotenüberdeckungszahl entspricht
	Dieser Satz von Menger (1927) ist eine Verallgemeinerung des Satzes von König (1916)
	so ist die kleinste Mächtigkeit einer a von B in G trennenden Teilmenge X von Va gleich der größten Mächtigkeit eines a-B-Fächers
	Man folgert aus ihm leicht den Fächersatz: Ist B eine Teilmenge von V und a Element von VB
	Man zeigt dies
	indem man A:=N(a) setzt (d.h
	A ist die Menge der Nachbarn von a) und den Satz von Mader anwendet
	so ist die kleinste Mächtigkeit einer a von b trennenden Teilmenge von V{a
	b} gleich der größten Mächtigkeit einer Menge disjunkter a-b-Wege in G
	so gilt: Sind a und b nicht benachbart
	Ganz ähnlich folgert man: Sind a und b zwei verschiedene Knoten von G
	Die kleinste Mächtigkeit einer a von b trennenden Teilmenge Y von E ist gleich der größten Mächtigkeit einer Menge kantendisjunkter a-b-Wege in G. Daraus lässt sich nun die globale Version des Satzes von Menger ableiten: G ist genau dann k-zusammenhängend
	wenn G zwischen je zwei Ecken k disjunkte Wege enthält
	wenn G zwischen je zwei Ecken k kantendisjunkte Wege enthält. [Bearbeiten]
	G ist genau dann k-fach kantenzusammenhängend
wichtige Algorithmen
	der die Zusammenhangskomponenten eines Graphen berechnet und so einen einfachen Test impliziert
	Mittels Tiefensuche lässt sich leicht ein linearer Algorithmus implementieren
	ob der Graph zusammenhängend ist
	ob ein gerichteter Graph von einem Knoten v aus zusammenhängend ist
	funktioniert analog
	Der Test
	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.

Dieser Artikel basiert auf dem Artikel Zusammenhang von Graphen aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.