Yacas Reloaded - Freies Computer Algebra System

Inhalt

Grundlagen der Mathematik

Diskrete Mathematik

Kombinatorik

Graphentheorie

Typen von Graphen

Nachbarschaft und Grad

Wege, Pfade, Zyklen und

Kreise

Isomorphie von Graphen

Operationen auf Graphen

Zusammenhang

Durchlaufbarkeit von

Graphen

Färbung

Paarungen in Graphen

Schnitte

Knotenüberdeckungen,

Cliquen und stabile Mengen

Differentialgleichungen

Funktionalanalysis

Differentialgeometrie

Anbieterkennzeichnung

Weiterbildung für alle! Über 200 Fernlehrgänge an Deutschlands größter Fernschule!

Zusammenhang von Graphen

Neu: Das Wurzelzieher Mathepedia Forum.

Jetzt registrieren und mit anderen Nutzern über Mathematik diskutieren!

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 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₁ ,...,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 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, 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 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. Eine Kante e heißt Brücke von G, wenn sie ihre beiden inzidenten Knoten trennt.

Man bezeichnet den Graphen, der

als Knotenmenge die Blöcke und Artikulationen von G enthält,
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.

Gerichtete Graphen

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. G heißt stark zusammenhängend, falls G von jedem Knoten v aus V 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 K=(V_K , E_K ) von G heißt starke Zusammenhangskomponente von G, falls K stark zusammenhängend ist und kein stark zusammenhängender induzierter Teilgraph von G exisitiert, der K echt enthält.

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.

Wichtige Aussagen und Sätze

Relativ leicht zeigt man folgende Aussagen:

Ein ungerichteter Graph ist genau dann zusammenhängend, wenn er einen spannenden Baum enthält.
Ein ungerichteter zusammenhängender Graph ist genau dann 2-zusammenhängend, wenn er keine Artikulation besitzt.
Die Knotenzusammenhangszahl ist höchstens so groß wie Kantenzusammenhangszahl und die Kantenzusammenhangszahl ist höchstens so groß wie der Minimalgrad.
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 einer 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 den 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:

Sind a und b nicht benachbart, 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.
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.
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 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 v 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.

Die ganzen Zahlen hat der liebe Gott geschaffen, alles andere ist Menschenwerk.

Leopold Kronecker

Druckansicht

Impressum: Wurzelzieher Mathepedia • Thomas Steinfeld • Dorfplatz 25 • 17237 Blankensee • Tel.: 01734332309 (Vodafone/D2) • Email: matһе@wυrzеlzιeher.de

Amazon.de empfiehlt: