12. Stabile Mengen

zurück zu Grundbegriffe II

12. Stabile Mengen

  • In einem Graphen X heißt eine Teilmenge W ⊂ V(X) innen stabil, wenn keine zwei ihrer Knoten adjazent sind.
  • Eine Knotenmenge W heißt maximal innen stabilgenau dann, wenn eine der folgenden Bedingungen erfüllt ist:
    • Kein Knoten x ∈ V(X) kann zu W hinzugefügt werden, ohne die innere Stabilität aufzuheben.
    • Alle Knoten der Differenzenmenge V(X)W haben mindestens einen unmittelbaren Nachbarn in W.

Die größte Anzahl von Knoten aller maximal innen stabilen Mengen gibt den Koeffizienten der inneren Stabilität (innerer Stabilitätskoeffizient) α(X) an.

12.1 Bestimmung der inneren stabilen Mengen

  1. Wir ordnen jeden Knoten xi eine Boolesche Variable i zu.
  2. Für alle Knoten xi ∈ V(X) Bildung des Booleschen Ausdrucks i + j.k.l…(j, k und l sind die Boolschen Variablen aller Knoten die mit xi adajazent sind)
    Beispiel: 1 + 2 * 4 * 5 ⇔ 1 ∨ 2 ∧ 4 ∧ 5 mit + … ∨ ist logische Summe und * … ∧ ist logisches Produkt
  3. Bildung des logischen Produkts aller Ausdrücke von Punkt 2
    (1 + 2 * 4 * 5)(2 + 1 * 3 * 5)(3 + 2 * 5 * 6)(4 + 1 * 5)(5 + 1 * 2 * 4)
  4. Äquivalenzumformung des so erhaltenen Ausdrucks mit Hilfe des Distributiv-, Absorptions- und Idempotenzgesetzes).
    Distributivgesetz:
    a ∨ (b ∧ c) ⇔ (a ∨ b) ∧ (a ∨ c)
    a ∧ (b ∨ c) ⇔ (a ∧ b) ∨ (a ∧ c)
    Verschmelzungs- oder Absorbtionsgesetz:
    a ∧ (a ∨ b) ⇔ a oder a ∨ (a ∧ b) ⇔ a
    Entsprechung: ∧ …. ∩ und ∨ ….. ∪
    Idempotenz: a ∨ a ⇔ a bzw. a ∨ a ⇔ a
  5. Ist keine Vereinfachung mehr möglich, so besteht der Boolesche Ausdruck aus einer logischen Summe logischer Produkte (DNF = Disjunktive Normalform).
  6. Jedes logische Produkt stellt eine Knotenmenge dar, deren Komplement in bezug auf die Knotenmenge des Graphen eine maximal innen stabile Knotenmenge ist.

Beispiel:

Nenne einige innen stabile Mengen.

{[2, 4, 6]}
{[1, 6]}, {[2,6]}, {[2, 4]}
{[3, 4]}, {[3, 1]}, {[4, 6]}
{1}, {2}, {3}, {4}, {5}, {6}

Algorithmus:
(1 + 2 * 4 * 5) (2 + 1 * 3 * 5) (3 + 2 * 5 * 6) (4 + 1 * 5) (5 + 1 * 2 * 3 * 4 * 6) (6 + 3 * 5)

(1 + 2 4 5) (2 + 1 3 5)

Damen auf Schachbrett –> dürfen sich nicht bedrohen

X
X
X
X

hier α(x) = 4 aber 8 Damen → 64 Felder → 92 Lösungen; α(x)=8

Man muss eine Knotenmenge finden, in der die Knoten paarweise untereinander nicht adjazent sind; daraus muss man die größtmögliche heraussuchen –> stabilen Mengen

X
X
X
X
X
X
X
X

{2,4} max {1}
{1,3} max {2}
{1,6} max {3}
{2,6} max {4}
{2,4,6} max {5} max
{3,4} max {6}
{4,6}

α(x) = 3

12.1.1 Genauere Vorgangsweise bei der Bestimmung der innenstabilen Menge

ad 1) Zuordnung: Knoten xi ⇐ i Boolesche Variable
i+j*k*l*K
mit xi adjazent

Idempotenz: a∧a⇔a und a∨a⇔a

(1+245)(2+135)(3+256)(4+15)(5+12346)(6+35)

+K∨ *;∧ (1∨2∧4∧5)∧(2∨1∧3∧5)K

(a+bx)(b+ay) ⇔ (a+bx)(b+y)
ab+ay+bx+abxy ⇔ ab+ay+bx+bxy
(der kürzere Ausdruck kommt im längeren vor → längere streichen)
aay ⇔ ay
a∧a∧y⇔a∧y

(1+245)(2+35)(3+56)(4+5)(5+6)

Adjazenzmatrix:
Adjazenzen für alle Verbindungen zw. den Knoten

Knoten-Knoten-(0,1)-Matrix

McCarthy-Schreibweise
aij([i,j]∈E(x) →1, sonst → 0)
symmetrische Matrix, weil der Graph ungerichtet ist.

1 2 3 4 5 6
1 1 0 1 1 0
2 1 0 1 0
3 0 1 1
4 1 0
5 1
6

a∨(a∧b)⇔a
(3,4,5,6)∪(3,5)

(1+245)(2+35)(3+56)(4+5)(5+6)
(1+245)(23+256+35+356)(45+46+5+56)
12346 + 1256 + 135 + 23456 + 2456 + 2345

{5} {3,4} {2,4,6} {1,3} {1,6} ∀ (x)=3

diese 5 Mengen sind alle maximal innen stabile Mengen.

Beispiel: Seminarorganisation

Es ist ein Seminar zu organisieren, dass aus 8 eintägigen Einzelveranstaltungen besteht.

Das Organisationskomitee möchte jeden Teilnehmer die Möglichkeit geben an allen Veranstaltungen teilzunehmen, zu denen er sich anmeldet.
Nach Ende der Anmeldefrist ergibt sich folgende Situation:

Anmeldungen
Teilnehmer Veranstaltungen
A 4,6,8
B 1,5
C 3,5
D 6,7
E 3
F 2,6
G 4,5,6
H 1,7
I 2,3
J 5,6
K 1,2
L 2,4,6
M 4,5
1 2 3 4 5 6 7 8
1 1 0 0 1 0 1 0
2 1 1 0 1 0 0
3 0 1 0 0 0
4 1 1 0 1
5 1 0 0
6 1 1
7 0
8

(1+257)(2+346)(3+5)(4+568)(5+6)(6+78)
(12+1346+257)(35+36+5)(46+478+568)
(12+1346+257)(346+34678+3568+456+4578+568)
12346 + 12456 + 124578 + 12568 + 1346 + 13456 + 1345678 + 134568
234567 + 24567 + 24578 + 25678
{3,7,8} {1,3,8}
{3,4,7} {1,3,6} für alle Möglichkeiten; man kann beliebige Auswahl treffen
{2,5,7,8} {1,3,4}
in 2 Tagen geht- nicht! min. 3 Tage:
{2,5,7,8}
{1,3,6}
{3,4,7}

12.2 Euler’she Linie

Typische Problemstellung:
Die Müllabfuhr muss bei jedem Haus vorbeifahren (Häuser stehen an den Kanten). Für alle gilt man muß alle Kanten befahren

Definition: geschlossene Euler’sche Linie = geschlossener Kantenzug, der jede Kante des Graphen genau 1 x enthält.

Ein Graph mit einer Euler’schen Linie heißt Euler’scher Graph

Ein zusammenhängender Graph hat genau dann eine Euler’sche Linie, wenn jeder Knoten geraden Grad hat.

Offene Euler’sche Linie:
offener Kantenzug, der jede Kante genau 1 x enthält, wenn es genau 2 Knoten ungeraden Grades gibt

einer davon ist der Startknoten, der andere der Endknoten
(Euler’scher Graph, nur bei geschl Euler’scher Linie)

12.3 Hamilton’sche Linie

Typische Problemstellung:
Das „Vertreterproblem“:
Zentrallager – an verschiedene Filialen ausliefern, auf kürzestem Weg alle Knoten abfahren.

Das führt zu einem Kreis, der jeden Knoten genau 1 x enthält.

Knoten stehen für Filialen und
Kanten für Straßen

Hamilton’scher Graph ist gegeben, wenn eine Hamilton’sche Linie existiert

d(x) muß 2 sein
∀ dæ(X)< 2 hätten wir eine offene Hamilton’sche Linie = Weg, der jeden Knoten genau 1 x enthält

Algorithmus:
(1 + 2 * 4 * 5) (2 + 1 * 3 * 5) (3 + 2 * 5 * 6) (4 + 1 * 5) (5 + 1 * 2 * 3 * 4 * 6) (6 + 3 * 5)
(1 + 2 4 5), (2 + 1 3 5)
1 → a, 2 → b, 4 und 5 → x, 2 →b, 1 → a, 3 und 5 → y
(a+ b x) (b + a y)

(a + bx)(b +ay) ⇔ (a + bx)(b+y) → nach dem Distributivgesetz: a∧a∧y
Frage: ab+ a a y + b b x + abxy ⇔ ab + ay + bbx + bxy
Antwort: JA, weil:
ab + aax + bbx + abxy ⇔ ab + ay + bbx + bxy

Streichung von aa und xy sowie bbx
p∨ (p∧q) = p (Streichung p∧q
p∧(p∨q) = p (streichen von (p∨q)

Betrachtungsweise mittels Mengen:

A ∪ (A ∩ B)
(1 + 2 4 5)(2 + 1 3 5)(3 + 2 5 6)(4 + 1 5)(5 + 1 2 3 4 6)(6 + 3 5)

Adajazenzmatrix:

1 2 3 4 5 6
1 1 1 1
2 1 1 1
3 1 1 1
4 1 1
5 1 1 1 1 1
6 1 1

(1 + 2 4 5) (2 + 3 5) (3 + 5 6) (4 + 5) (5 + 6)

weiter distribuieren:

(1 2 + 1 3 5 + 2 4 5) (3 + 5 6) (4 5 + 4 6 + 5 + 5 6)
(1 2 + 1 3 5 + 2 4 5) (3 4 6 + 3 5 + 4 5 6 + 5 6)
1 2 3 4 6 + 1 2 3 5 + 1 2 5 6 + 1 3 4 5 6 + 1 3 5 + 1 3 5 6 + 2 3 4 5 6 + 2 3 4 5 + 2 4 5 6

DNF: (1 2 3 4 5) ∨ (1 2 5 6) ∨ (1 3 5) ∨ (2 3 4 5) ∨ (2 4 5 6)

Komplement:

W = { 5 }
W = {[3,5]}
W = {[2,4,6]}
W = {[1,6]}
W = {[1,3]}
alle innen stabile Mengen des Graphen (Anzahl der stabilen Mengen)

Innerer Stabilitätskoeffizient: α(X) = 3 wegen W={[2,4,6]}

nach oben

 

(274)

11. Trennende Mengen

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)

10. Artikulationen, Blöcke, Brücken

zurück zu Grundbegriffe II

10. Artikulationen, Blöcke, Brücken

10.1 Äquivalente Aussagen überprüfen

Aussage_1 ↔ Aussage_2 ↔ ….. ↔ Aussage_n
Ersetzen der Äquivalenz durch eine Implikation

(Aussage_1 → Aussage_2) ∧ (Aussage_2 → Aussage_1) ∧ (Aussage_2 → Ausage_n
iann ersetzt werden durch die abgekürzte Version
(Aussage_1 → Aussage_2) ∧ (Aussage_2 → Aussage_n) ∧ (Aussage_n → Ausage_1)

Dadurch wird der Ring geschlossen, es bedarf nur |n| Überprüfungen, ob die Aussagen äquivalent sind.

10.1.2 Block

Die jeweils größten zusammenhängende Teilgraphen eines Graphen, der keine Artikulationen aufweist, nennt man Block. Ein Graph kann n Blöcke haben.

Eine Kante gehört immer genau zu einem Block, sie kann niemals in mehreren Blöcken liegen.

Der kleinste Block besteht einem Graphen mit nur einem Knoten, wenn mehr als 1 Knoten, dann aus 2 Knoten und eine Kante, welche mit diesen Knoten inzident ist.

Ein gesättigterTeilgraph X1 von X heißt Block von X, wenn X1 zusammenhängend und ohne Artikulation ist, aber kein Teilgraph X2 von x mit V(X2) ⊃ VX1) diese Eigenschaft besitzt.

10.1.3 Artikulation

Ist jener Knoten, wenn beim Entfernen dieses Knoten der Graph mehr Komponenten besitzt als zuvor, also nicht mehr zusammenhängend ist.

Eine Artiikulation ist jene Schwachstelle in einem Graphen, da sie die einzige Verbindung einen Weg unter allen Knoten schafft. Aus diesem Grund sollten Artikulationen vermieden werden.

Ist eine Schnittstelle von mindestens 2 bis n Blöcken.

Satz: Zwei Blöcke eines Graphen haben höchstens einen gemeinsamen Knoten und dieser ist Artikulation von X.

Folgerung 1: Ein Knoten x ist Artikulation von X genau dann, wenn x in mindestens zwei Blöcken liegt.

Folgerung 2: Jede Kante und jeder Kreis von X liegen in genau einem Block von X.
(d.h. es gibt keine Kante die in zwei Blöcken liegt).

Ist F ⊂ E(X) eine Menge von Kanten von X, so ist der Graph X-F definiert durch:
V(X-F) = V(X)
E(X-F) = E(X)F

Seperabler Graph:
Ein zusammenhängender Graph mit mindestens einer Artikulation.

10.1.4 Brücken

Eine Kante ist dann eine Brücke, wenn der Graph nach dem Entfernen der Kante mehr Komponenten besitzt als vorher.

Brücke entfernen: Zusammenhängender Graph zerfällt in genau 2 Komponenten
Artikulation entfernen: Zusamenhängender Graph zerfällt in mindestens 2 Komponenten, bis maximal |V(x)-1| Komponenten

Brücken verbinden:

  • 2 Artikulationen
  • 2 Endpunkte
  • 1 Artikulation mit 1 Endpunkt

Eine Kante e ∈ E(X) heißt Brücke von X, wenn X -{e} mehr Komponenten besitzt als X.

Eine trennende Kantenmenge in einem zusammenhängenden Graphen X ist eine Teilmenge T ⊂ E(X), so dass X-T nicht zusammenhängend ist. Ein Schnitt ist eine minimale trennende Kantenmenge.

Satz: Es sei X ein zusammenhängender Graph mit |V(X)| ³ ≥ 3. Dann sind folgende Aussagen äquivalent:

  • X ist ein Block.
  • Durch je zwei Knoten von X geht ein Kreis.
  • Durch je zwei Kanten von X geht ein Kreis.
  • Sind x ≠ y (unterschiedliche Knoten) aus V(X) und e ∈ E(X) beliebig, so gibt es einen Weg von x nach y der e enthält.
  • Für je drei verschiedene Knoten x,y,z aus V(X) gibt es einen Weg von x nach y der über z führt.
  • Für je drei verschiedene Knoten x,y,z aus V(X) gibt es einen Weg von x nach y, der nicht über z führt.

Wiederholung

Artikulation: ……Der Durchschnitt zweier Blöcke ist eine Artikulation

Block:…………..Größtmöglicher Teilgraph ohne Artikulationen des Teilgraphen,
Jeder Block mit mehr als 2 Knoten ist auch ein Kreis

Brücke:………….Jede Brücke ist auch ein Block

Kreis:…………..Jeder Kreis umschließt genau einen Block

Kante:…………..Jede Kante liegt genau in einem Block

10.3 Bestimmung von Artikulationen, Blöcken, und Brücken

10.3.1 Algorithmus

  1. Ausgangsknoten wählen
  2. alle inzidenten Kanten des Knoten mit einem Strich markieren, wenn diese noch keinen Kreis bilden
  3. entsteht ein Kreis und keine Kante gehört bereits zu einem früheren Kreis, vergebe für alle Kanten einen eindeutigen Buchstaben, ansonst wird der Buchstaben des früheren Kreises verwendet.
  4. die letzte Kante, welche keinen Kreis bildet bestimmt den nächsten Knoten, gehe zu Punkt 2
  5. wenn alle Knoten untersucht wurden, bestimmen alle mit dem selben Buchstaben markierten Kanten einen Block, alle mit einem Strich markierten Kanten sind Brücken und daher auch eigenständige Blöcke. Alle möglichen Durchschnitte der Knotenmengen je zweier Blöcke ergeben die Artikulationen.

Artikulationen: V = {e,g}
Blöcke: Block A: V = {a,b,c,d,e}
Block B: V = {e,f,g}
Block C: V = {g,h,i,j}
Block D: V = {e,k}

Brücken: E = {D}

nach oben

(1257)

9.) Zusammenhang und Komponenten

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)

8. Kreis, Abstand

zurück zu Grundbegriffe II

8. Kreis, Abstand

Def.: Ein Kreis ist ein geschl. Kantenzug, bei dem die Knoten x1,x2,…xn-1 alle verschieden sind (geschlossener Weg).

Die Anzahl der Kanten in einer Kantenfolge heißt die Länge der Kantenfolge. (|KF(x,y|)

Der Abstand d(x,y) zweier Knoten ist die kleinste Länge eines Weges von x nach y, falls es solche Wege gibt.

d(x,y) = min | W(x,y)|
Andernfalls setzt man d(x,y) = ∞

d(x,y) = d(x,y) für alle x,y ∈ V(X)

d(x,y) ≤ d(x,z) + d(z,y) Dreiecksungleichung

In jedem Graphen mit X = (V,E) gilt:

Die Anzahl der Knoten bei einem Graphen ist gerade, wenn die Knotengrade ungerade sind. Jede Kantenfolge von x1 nach xn enthält einen Weg von x1 nach xn.

Beispiel:

  1. [1,2],[2,5],[5,3],[3,2][2,1] …………kein Weg, kein Zug, geschl. KF
  2. [1,6],[6,7],[7,8],[8,4][4,8] ……………….“-”
  3. [2,3],[3,4],[4,8],[8,9] ……………..kein Kantenzug; Kante 89 nicht vorhanden
  4. [1,2],[2,5],[5,3],[3,2] ……………..Kantenzug; kein Weg; Knoten 2 2mal vorh.
  5. [3,5],[5,8],[8,4],[4,3] ……………..Kreis
  6. [6,7],[7,9],[9,0],[0,8],[8,4] ………..Weg
  7. [7,8],[0,8],[0,9] …………………..Weg
  8. [6,7],[7,6],[6,7],[7,6] ……………..geschl. KF

Distanz:
d(3,7) = 3
d(4,4) = 0
d(1,0) = 4
d(1,11) = ∞
d(7,0) = 2
d(3,0) = 3

Aus Kantenfolgen einen Weg erstellen:

  1. x1 = xn Jeder Knoten ist ein Weg zu sich selbst
  2. x1 ¬ xn solange alle Kanten zwischen dem 1. und dem 2. Erreichen eines Knoten entfernen, dadurch entsteht ein Weg, die direkte Verbindung zwischen x1 und xn.

8. 1 Das Bauer, Krautkopf, Ziege, Wolf Problem

Ein Bauer hat einen Wolf, eine Ziege, einen Krautkopf und ein Boot. Sie stehen vor einem Fluss und müssen ihn überqueren. Das Boot kann maximal 2 gleichzeitig befördern (großer Krautkopf!) und es ist zu bedenken, dass der Wolf die Ziege frisst und die Ziege den Krautkopf, wenn man sie alleine lässt. Nur Wolf und Kraut dürfen alleine auf einem Ufer bleiben.
Es gibt dafür mehrere Lösungen, z.B.: Ziege mitnehmen – leer zurück – Kohl mitnehmen – Ziege zurück – Wolf mitnehmen – leer zurück – Ziege mitnehemen, oder eine andere Möglichkeit wäre: Ziege mit – leer zurück – Wolf mit – Ziege zurück – Kraut mit – leer zurück -leer hin und her, so oft es Spaß macht – Ziege mit…
der kürzeste Weg ist zu ermitteln.

mögliche Zustände an einem Ufer:

B,Z,W,K – B,W,Z – B,W,K – B,Z,K – B,Z und am anderen Ufer
– -{} —- K —– Z —– W —- W,K

1.1.1 Lösung zum Beispiel „Der Wolf, die Ziege und der Krautkopf“

  1. Man betrachte alle möglichen Zustände auf einem Ufer. Bei 4 Beteiligten ergibt das 42 Möglichkeiten. ({}, B, W, K, Z, BW, BZ,BK,WZ, WK, KZ, BWZ, BWK, BKZ, WKZ, BWKZ) Da jeder Zustand eines Ufers den Komplimentärzustand des anderen Ufers darstellt, braucht man nur ein Ufer darstellen.
  2. man streiche laut den Nebenbedingungen alle Zustände, welche nicht möglich sind
  3. übrig bleiben ({}, W, K, Z, BZ, WK, BWK, BKZ, BWZ, BWKZ)
    und diese restlichen Zustände ergeben je einen Knoten im Graphen
  4. jeder Knoten wird überprüft, ob er mit einem anderen Knoten adjazent sein kann aufgrund der Nebenbedingungen. Somit kann kein Knoten, bei dem der Bauer beteiligt ist mit einem Knoten adjazent sein, bei dem der Bauer auch beteiligt ist, sonst würde das Boot ohne Bauer alleine fahren. Man ziehe alle möglichen Kanten der Reihe nach
  5. man suche die kürzesten Wege bzw. den kürzesten Weg in der Kantenfolge vom Ausgangzustand bis zum deffektiven Endzustand.

Sowohl die gestrichelte Linie, als auch die fette Linie stellen einen Weg vom Zustand B,W,Z,K zum Zustand {} dar, wobei die Wege jeweils eine Kantenlänge von 7 haben.
Ufer A: (B,W,K,Z) – (K,W) – (K) – (Z) – {}
Ufer B: {} – (Z) – (W) – (K,W) – (B,W,K,Z) oder
Ufer A: (B,W,K,Z) – (K,W) – (W) – (Z) – {}
Ufer B: {}- (Z) – (K) – (K,W) – (B,W,K,Z)

Potenzmenge – Summe aller Möglichkeiten in einer Menge.

nach oben

(295)