9.) Zusammenhang und Komponenten

(Last Updated On: 19. Oktober 2012)

zurück zu Grundbegriffe II

9 Zusammenhang und Komponenten

Ein Graph heißt zusammenhängend, wenn je zwei seiner Knoten durch einen Weg miteinander verbunden sind.

Die (Zusammenhangs-) Komponente K(x) des Knotens x ist die Menge aller Knoten y, die mit x durch einen Weg verbunden sind.

K(x) = {y|∃ W(x,y)}

Λ=∀ und V = ∃

Satz: sind x ≠ y zwei Knoten des Graphen X und ist K(x) ∩ K(y) ≠ {}, so ist K(x) =K(y).

Die von den K(x) aufgespannten, gesättigten Teilgraphen von X heißen die Komponenten von X.

Durchnmesser von X: diam(X) = dm(X) = max d(x,y) x,y ∈ V(X)

K(a) = {a,b,c,d,e,f}
K(b) = K(f)

Beweis: q → p; ¬q → ¬p

K(x) ∩ K(/y) ≠ {} → ∃ z ∈ K(x) ∩ K(y) → z ∈ K(x) ∧ z ∈ K(y)
∃ W(x,y) ∧ ∃ W/(z,y) → V(x,z) ∨ W(z,y) → ∃ W(x,y) ⊆ KF(x,y)
K(y)⊆K(x) und K(x)⊆K(y) ⇒ K(x) = K(y)

9.1 Zusammenhängende Graphen

Ein Graph heißt zusammenhängend, wenn zw. Je zwei Ecken ein Kantenzug existiert.

Für top. Graphen ist dieser Zusammenhang mit dem Wegzusammenhang identisch.

Jeder nichtzusammenhängender Graph läßt sich in maximal zusammenhängende Komponenten zerlegen. Für einen endl., schlingen- und zweiecklosen Graphen gilt:

nk ≤ ½ (ne -z) (ne -z + 1). Ein endl., schlingen- und zweiecklosen Graphen mit mehr als ½ne -2) (ne -1) Kanten ist daher zusammenhängend.

Eulersche Linien sind nur im zusammenhängenden Graphen möglich. Es gilt:

In einem endl. Graphen existieren genau dann eine eulersche Linie, wenn der Graph zusammenhängend ist und jeder Eckgrad gerade ist (genau zwei Ecken ungerade)sind). Das Königsberger Brückenproblem hat daher keine Lösung. Vergleichbare Kriterien für Hamiltonsche Linien sind nur für spez. Graphen bekannt.

Bem.: Ein endl. Graph, in dem jeder Eckgrad gerade ist, heißt auch Eulerscher Graph.

9.1.1 Zusammenhang und Komponenten

Graph X: (nicht zusammenhängend): K(1) = {1,2,4,5} = K(2) = K(4) = K(5)
K(3) = {3,6,7} = K(6) = K(7)
Es gibt 7 Zusammenhangskomponenten, welche aber in 2 unterschiedlichen Mengen vorhanden sind.

Graph Y: (zusammenhängend)

Ein Graph ist zusammenhängend, wenn von jedem Knoten ein Weg zu allen anderen Knoten führt.

9.1.2 Zusammenhangskomponente K(x)

Die Menge aller Knoten y, welche mit dem Konten x durch einen Weg verbunden sind.

  • K(x) = {y|∃ W(x,y)}
  • V(G) = {a,b,c,d,e,f,g,h,i}
  • E(G) = {[a,b], [a,c], [b,c], [b,i], [d,e], [d,f], [d,h], [e,f], [e,h], [f,h]}
  • K(a) = {a,b,c,i} = K(b) = K(c) = K(i)
  • K(d) = {d,e,f,h} = K(e) = K(f) = K(i)
  • K(g) = {g}

9.1.3 Komponenten

Sind zusammenhängende, aufgespannte, gesättigte Teilgraphen eines Graphen.

  • K1 = (K(a), {[a,b], [a,c], [b,c], [b,i]})
  • K2 = (K(d), {[d,e], [d,f], [d,h], [e,f], [e,h], [f,h]})
  • K3 = ({g}, {})

9.1.4 Durchmesser

Der Durchmesser ist der kürzeste Weg zwischen den am weitest entfernten Knoten innerhalb eines Graphen.

diam(X) = dm(X) = max d(x,y)/x,y ∈ V(X)

9.1.5 Durchschnitt zweier Zusammenhangskomponenten

x ≠ y, K(x), K(y) zwei Knoten (x, y) eines Graphen sind ungleich, es gibt je eine Zusammenhangskomponente
K(x) ∩ K(y) ≠ { } der Durchschnitt der beiden Zusammenhangskomponenten ist nicht die leere Menge
∃ z !z∈ K(x) ∧ z ∈ K(y) es existiert ein Knoten z, welcher sowohl in der Zusamenhangskomponente des Knoten x als auch des Knoten y enthalten ist
W(x,z) ∧ W(z,y) dann gibt es sowohl einen Weg zwischen den Knoten (x,z) als auch zwischen (z,y)
W(x,z) ∪ W(z,y) durch die Vereinigung des Weges (x,z) mit dem Weg (z,y)
∃ KF(x,y) existiert eine Kantenfolge zwischen den Knoten (x,y), wo eine Kantenfolge besteht
∃ W(x,y) existiert auch ein Weg zwischen den Knoten (x,y)
K(y) ≤ K(x)
K(x) ≤ K(y) somit muß die Komponente von y eine Teilmenge der Komponente von x und umgekehrt sein
K(x) = K(y) somit muß die Komponente von x ident mit der Komponente von y sein

9.1.6 Löschen von Knoten in einem Graphen

Graph X, A ⊂ V(X), löschen von A
V(X-A) = V(X)A
E(X-A) = {[x,y] | [x,y] ∈ E(X), x ∉ A ∧ y ∉ A}

Wenn von einem Graphen X der Knoten A gelöscht wird:
Knotenmenge = X – A
Kantenmenge = alle Kanten des Graphen X, ausgenommen jenen Kanten, welche mit dem Knoten A inzident (verbunden) sind

Ist X ein Graph und A ⊂ V(X), so erhält man durch Löschen von A in X, symbolisch X-A, folgenden Graphen:
V(X-A) = V(X)A
E(X-A) = {[x,y]|[x,y] ∈ E(X), x ¬isin;

nach oben

(298)


History

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert