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
- Ausgangsknoten wählen
- alle inzidenten Kanten des Knoten mit einem Strich markieren, wenn diese noch keinen Kreis bilden
- 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.
- die letzte Kante, welche keinen Kreis bildet bestimmt den nächsten Knoten, gehe zu Punkt 2
- 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}