Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMittwoch, 23. Juli 2014 

Zusammenhang von Graphen


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

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. Falls G nicht zusammenhängend ist nennt man G unzusammenhängend .

Sind A B und X Teilmengen von V und ist Y Teilmenge von E so nennt man Z =( X Y ) einen A-B-Trenner in G falls für jeden A - B -Weg ( v 1 ... v k ) in G ein i aus {1 ... k } oder ein j aus {1 ... k -1} existiert so dass v i Element von X oder { v j v j +1 } Element von Y ist. Man sagt dann dass Z die Knotenmengen A und B in G trennt . Statt "( X {}) bzw. ({ v } {}) bzw. ({} Y ) bzw. ({} { 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 V \ X trennt.

G heißt k-fach kantenzusammenhängend wenn es keine maximal k -1 elementige Kantenmenge in G gibt die G trennt (in Multigraphen kann man Kanten entsprechend ihrer Vielfachheit 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 wenn es keine maximal k -1-elementigen Knotenmenge in G gibt 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.

Ist U eine Teilmenge von V mit der Eigenschaft 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 dass der von W induzierte Teilgraph G [ W ] von G k -zusammenhängend ist so nennt man G[U] eine k-Zusammenhangskomponente von G . Eine 1-Zusammenhangskomponente nennt man auch einfach 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. Eine Kante e heißt Brücke von G wenn sie ihre beiden inzidenten Knoten

Man bezeichnet den Graphen der

  1. als Knotenmenge die Blöcke und Artikulationen von G enthält
  2. eine Artikulation a mit einem Block B verbindet falls a in G zu B gehört und
  3. sonst keine weiteren Kanten besitzt
als Blockgraph von G .

Ein gerichteter Graph G =( V E ) heißt zusammenhängend von einem Knoten v aus falls es zu jedem Knoten w aus V einen gerichteten Weg in G gibt mit v als Startknoten und w als Endknoten. 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.

Ein induzierter Teilgraph K =( V K E K ) von G heißt starke Zusammenhangskomponente von G falls K stark zusammenhängend ist und in G kein Knoten aus V K Vorgänger oder Nachfolger von einem Knoten aus der Differenzmenge V \ V K 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 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 er einen spannenden Baum enthält.
  2. Ein ungerichteter zusammenhängender Graph ist genau dann wenn er keine Artikulation besitzt.
  3. Die Knotenzusammenhangszahl ist höchstens so groß wie und die Kantenzusammenhangszahl ist höchstens so groß der Minimalgrad.
  4. Der Blockgraph G B eines Graphen G ist ein Wald . G B ist genau dann Baum (also zusammenhängend) 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 Menge disjunkter A - B -Wege in G . 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 Fächersatz:

Ist B eine Teilmenge von V und a Element von V \ B so ist die kleinste Mächtigkeit einer a von B in G trennenden Teilmenge X von V \ a gleich der größten Mächtigkeit eines a - B - Fächers . 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 so gilt:

  1. Sind a und b nicht benachbart so ist die kleinste einer a von b trennenden Teilmenge von V \{ a b } gleich der größten Mächtigkeit einer Menge disjunkter a - b -Wege in G .
  2. Die kleinste Mächtigkeit einer a von b trennenden Teilmenge Y von E ist gleich der größten Mächtigkeit einer Kantendisjunkter a - b -Wege in G .

Daraus lässt sich nun die globale des Satzes von Menger ableiten:

  1. G ist genau dann k -zusammenhängend wenn G zwischen je zwei Ecken k disjunkte Wege enthält.
  2. G ist genau dann k -fach kantenzusammenhängend wenn G zwischen je zwei Ecken k kantendisjunkte Wege enthält.

wichtige Algorithmen

Mittels Tiefensuche lässt sich leicht ein linearer Algorithmus der die Zusammenhangskomponenten eines Graphen berechnet und einen einfachen Test impliziert ob der Graph ist. Der Test ob ein gerichteter Graph einem Knoten v aus zusammenhängend ist funktioniert analog. Von ( 1972 ) stammt ein linearer Algorithmus der ebenfalls Tiefensuche basiert und in gerichteten Graphen die Zusammenhangskomponenten und leicht modifiziert in ungerichteten Graphen Blöcke und Artikulationen berechnet.

Zur Berechnung von Knoten- und Kantenzusammenhangszahl es polynomielle Algorithmen . Dazu kann man beispielsweise Flussalgorithmen verwenden. Allerdings gibt es auch effizientere



Bücher zum Thema Zusammenhang von Graphen

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Zusammenhangskomponente.html">Zusammenhang von Graphen </a>