11. Trennende Mengen

(Last Updated On: 19. Oktober 2012)

zurück zu Grundbegriffe II

11. Trennende Mengen

Knoten

x, y ∈ V(x), x ≠ y

[x,y] ∈ E(x)

U ⊆ kV(x) heißt eine x und y trennende Knotenmenge, wenn x und y in X-U in verschiedenen Komponenten liegen.

U = {φ} x,y trennende Knotenmenge

Z.B.

Trennende Mengen bei diesem Baum für die Knoten c und e sind:
{b}, {a}, {d}

Trennende Mengen bei diesen Graphen für die Knoten c und e sind:
{d}, {b,f}, {a,f}, {a,b,f}, {b,d}, {a,d}, {d,f}, {a,b,d}, {a,d,f}, {a,b,d,f}

Dabei ist bei den trennenden Mangen nur die kleinste trennende Menge interessant, da dadurch die Stabilität im Graphen gekennzeichnet wird.

Trennende Mangen gibt es immer, sie kann auch die leere Menge sein, wenn die zwei Knoten bereits von einander isoliert sind.

11.1 2 Knoten eines Graphen sind nicht adjazent

2 Knoten eines Graphen sind nicht miteinander verbunden und sie sind nicht ident.
x,y ∈V/X), (x,y) ∉ E(X), x ≠y
U ⊆ V(X) …………… Knotenteilmenge des Graphen X
Die Menge U heißt eine x,y trennende Knotenmenge,
wenn x,y in X – U in verschiedenen Komponenten liegen
τ = Knotentrennungszahl:
τ(x,y)=min|U|………………..Tau von x,y = die minimale Anzahl von Elementen die trennen. τ ist die Knotentrennungszahl zweier konkreter Knoten, je kleiner der Wert von Tau ist , desto instabiler ist der Graph. Z.B. Maßzahl für die Stabilität eines Netzwerks.
Beim Baum und beim Graphen darunter ist τ (c,e) = 1
Beim Graphen darunter ist τ (c,d) = 2

κ = Knotenzusammenhangszahl:
κ(X) = minτ(x,y) x,yy ∈ V(x)……………..Kappa ist die minimale Knotenzusammenhangszahl des gesamten Graphen, aus allen Tau aller Knotenkombinationen, wird das Minimum genommen.

κ = 0 mind 2 Komponenten
κ = 1 enthält eine Artikulation (zusammenhängend)
κ(Cn) = n-1; Cn = vollständiger Graph

ω(x,y) ………………….. Omega von x u. y = Anzahl der knotendisjunkten Wege zwischen Knoten x und y, jeder Weg zwischen den Knoten x u. y muß unterschiedliche Knoten aufweisen, kein Knoten wird 2 mal verwendet.

Satz von Menger:

τ(x,y) =ω(x,y) ………… Die Knotentrennungszahl Tau zweier Knoten ist gleich die Anzahl der Knotendisjunkten Wege zwischen denselben Knoten.

τ‾(x,y) = ω‾(x,y) ………….. Die Kantentrennungszahl Tau quer zweier Knoten ist gleich die Anzahl der Kantendisjunkten Wege zwischen denselben Knoten (disjunkt = elementenfremd).

11.2 2 Knoten eines Graphen können adjazent sein (Kanten)

2 Knoten eines Graphen sind nicht ident.
x,y ∈V(X), x≠y und [x,x]∈E(x)

F ⊆ E(X) ……………. Kantenteilmenge des Graphen X
Die Menge F heißt eine x,y trennende Kantenmenge,
wenn x,y in X – F in verschiedenen Komponenten liegen bzw.
F ⊆ kV(x) heißt eine x und y trennende Kantenmenge, wenn x und y in X-F in verschiedenen Komponenten liegen.
F = m {[a,y], [c,y]}

τ‾(x,y) = min|F| ……………… Tau quer von x,y = die minimale Anzahl von Elementen die trennen
Ist die Kantentrennungszahl zweier konkreter Knoten, je kleiner der Wert von Tau ist, desto instabiler ist der Graph.

κ‾(X) 0 minτ‾(x,y) …………… Kappa quer ist die minimale Kantenzusammenhangszahl des gesamten Graphen, aus allen Tau quer aller Kantenkombinationen, wird das Minimum genommen.

ω‾(x,y) …………… Omega quer von x, y ist die Anzahl der Kantendisjunkten Wege zwischen Knoten x und y, jeder Weg zwischen den Knoten x u. y muß unterschiedliche Kanten aufweisen, keine Kante wird 2 mal verwendet.

κ(x) min τ‾(x,y)
x,y ∈ V(x)
κ = Kantenzusammenhangszahl
κ = 0 mindestens 2 Komponenten
κ = 1 enthält eine Brücke (zusammenhängend)
κ ⟩ 1
ω(x,y) Kantendisjunkt
Satz von Menger: τ‾(x,y) = ω‾(y,y)

11.2.1 Beispiele

  • κ(X) = 0 ……….. der Graph ist nicht zusammenhängend, da die Knotenzusammenhangszahl 0 ist, ist die kleinste trennende Knotenmenge die leere Menge
  • κ(X) = 1 ……….. der Graph hat mindestens 1 Artikulation u. ist zusammenhängend, Artikulation, da er durch Wegnahme eines einzigen Knoten in mehrere Komponenten zerfällt, zusammenhängend, sonst müßte die die kleinste trennende Knotenmange die leere Menge sein
  • κ(X) = 2 ……….. der Graph ist zusammenhängend, hat keine Artikulationen und der gesamte Graph ist ein Block, denn man muss mindestens 2 Knoten entfernen, damit der Graph in zwei Komponenten zerfällt, ohne Artikulationen besteht der Graph nur aus einem Block
  • κ‾(X) = 0 …. der Graph ist nicht zusammenhängend, da die Kantenzusammenhangszahl Null ist, ist die kleinste trennende Kantenmenge die leere Menge
  • κ‾(X) = 1 …. der Graph ist zusammenhängend, weißt jedoch mindestens eine Brücke auf, da er durch Wegnahme einer einzigen Kante in mehrere Komponenten zerfällt, sonst müßte die die kleinste trennende Kantenmange die leere Menge sein
  • κ‾(X) = 2 …. der Graph ist zusammenhängend, hat keine Brücken und jede Kante ist in einem Kreis, über Artikulationen wird nichts ausgesagt
  • κ(X) ≥ n …. Kappa n-fach, n-fach knotenzusammenhängend
  • κ‾(X) ≥ n …. Kappa quer n-fach, n-fach kantenzusammenhängend

Wenn jede Kante in einem Kreis, dann ist das Kappa quer des Graphen noch unbestimmt, jedoch gilt, dass κ‾(X) ≥ 2, da ein Kreis nur durch entfernen von mindest 2 Kanten in zwei Komponten zerfallen kann.

Reguläre Graphen von Grad 1 mit κ(X) = 0 sind jeweils 2 Knoten adjazente Knoten, welche im Graphen mehrfach vorkommen.

Reguläre Graphen von Grad 2 mit κ(X) = 1 gibt es nicht. Dadurch gibt es jeden regulären Graphen mit κ(X) = 0, der Graph muß nur 2 oder mehrere Komponenten aufweisen.

  1. Wie bestimme ich Tau von x,y = τ(x,y)?
    Wenn man die Knoten markiert mit dem Quadrat entfernt liegen die Knoten x,y in verschiedenen Komponenten, Anzahl der entfernten Knoten τ(x,y) = 2
  2. Wie bestimme ich Tau quer von x,y = τ‾(x,y)?
    Durch Entfernen der durchgestrichenen Kanten liegen die Knoten x,y in verschiedenen Komponenten Anzahl der entfernten Kanten τ‾(x,y) = 3
  3. Wie bestimme ich Omega von x,y = ω(x,y)?
    Man gehe verschiedene Wege (voll und strichliert), wenn kein Weg mehr vorhanden, welcher nur Knoten aufweist, welche noch nicht verwendet, dann Weganzahl ω(x,y) = 2
  4. Wie bestimme ich Omega quer von x,y = ω‾(x,y)?
    Man gehe verschiedene Wege (voll, strichliert, gepunktet), wenn kein Weg mehr vorhanden, welcher Kanten aufweist, welche noch nicht verwendet, dann Weganzahl ω‾(x,y) = 3

Der Knotengrad eines Graphen sagt nichts über die knoten-kanten-disjunkten Wege aus, da Graphen mit mehreren Knoten vom Knotengrad 5 auch eine Brücke od. eine Artikulation aufweisen können.

Raid 5 ist ein min. 2fach zusammenhängender Speichergraph.

nach oben

(586)


History

Schreibe einen Kommentar

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