Stichpunkte

Allgemein
	[Bearbeiten]
Definitionen
	E) heißt zusammenhängend
	Ein ungerichteter Graph G=(V
	mit v als Startknoten und w als Endknoten
	falls es zu je zwei beliebigen Knoten v und w aus V einen ungerichteten Weg in G gibt
	Falls G nicht zusammenhängend ist
	nennt man G unzusammenhängend
	k} oder ein j aus {1
	...
	...
	vk) in G ein i aus {1
	Y) einen A-B-Trenner in G
	...
	vj+1} Element von Y ist
	Sind A
	so dass vi Element von X oder {vj
	k-1} existiert
	B und X Teilmengen von V und ist Y Teilmenge von E
	falls für jeden A-B-Weg (v1
	so nennt man Z=(X
	Man sagt dann
	dass Z die Knotenmengen A und B in G trennt
	Y) bzw. ({}
	{e}) trennt A und B in G" sagt man auch "X bzw. v bzw
	{}) bzw. ({}
	{}) bzw. ({v}
	Statt "(X
	Y bzw. e trennt A und B in G"
	wenn Z in G zwei Ecken aus VX trennt
	Allgemeiner sagt man Z trennt G
	die G trennt (in Multigraphen kann man Kanten entsprechend ihrer Vielfachheit mehrfach entfernen)
	wenn es keine maximal k-1 elementige Kantenmenge in G gibt
	G heißt k-fach kantenzusammenhängend
	sodass G k-fach kantenzusammenhängend ist
	Als Kantenzusammenhangszahl eines Graphen G bezeichnet man das größte k
	wenn es keine maximal k-1-elementigen Knotenmenge in G gibt
	G heißt k-fach knotenzusammenhängend
	die G trennt
	Statt k-fach knotenzusammenhängend sagt man auch oft kürzer k-fach zusammenhängend oder k-zusammenhängend
	Als Knotenzusammenhangszahl eines Graphen G bezeichnet man das größte k
	sodass G k-zusammenhängend ist
	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
	Ist U eine Teilmenge von V mit der Eigenschaft
	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
	eine Artikulation a mit einem Block B verbindet
	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
	falls es zu jedem Knoten w aus V einen gerichteten Weg in G gibt
	Ein gerichteter Graph G=(V
	mit v als Startknoten und w als Endknoten
	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
	wenn es einen Pfad mit v als Startknoten und w als Endknoten gibt
	Bemerkung: Es gibt genau dann einen Weg mit v als Startknoten und w als Endknoten
	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
	Ganz ähnlich folgert man: Sind a und b zwei verschiedene Knoten von G
	b} gleich der größten Mächtigkeit einer Menge disjunkter a-b-Wege in G
	so gilt: Sind a und b nicht benachbart
	so ist die kleinste Mächtigkeit einer a von b trennenden Teilmenge von V{a
	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
	ob der Graph zusammenhängend ist
	Mittels Tiefensuche lässt sich leicht ein linearer Algorithmus implementieren
	funktioniert analog
	Der Test
	ob ein gerichteter Graph von einem Knoten v aus zusammenhängend ist
	der ebenfalls auf Tiefensuche basiert und in gerichteten Graphen die starken Zusammenhangskomponenten und leicht modifiziert in ungerichteten Graphen die Blöcke und Artikulationen berechnet
	Von Tarjan (1972) stammt ein linearer Algorithmus
	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.