zurück zu Allgemeines

1      Graphentheoretische Algorithmen

1.1  Algorithmus zur Konstruktion eines maximalen Matchings

Matching maximal Û es existiert kein erweiterter alternierender Weg.

Initialisierung:

Step1: Aufnahme von paarweise disjunkten Kanten in einer Menge M (soviele wie möglich).

i=0, Mo = M;

Iteration:

Step2: Gibt es einen erweiterten alternierenden Weg W des Matchings Mi, dan ist Mi+1 =

(Mi-W) È (W-Mi) (= Mi D  W).

goto Step 3

Gibt es keinen alternierenden Weg, so gogo Step 4.

Step3:  i=i+1, goto Step2

Abschluß:

Step4: Mi ist das maximale matching.

 

1.2  Algorithmus zur Untersuchung eines gerichteten Graphen auf Azyklizität

G azyklisch -> $ x mit d+(x) = 0

Algorithmus:

Step1: Wir markieren alle Punkte x mit d+(x) =0 mit der Marke +.

Step2: jeder Punkt mit der Eigenschaft, daß alle seine Nachfolger mit + markiert sind, wird auch mit + markiert. Step 2 wird so oft wiederholt, als neue Punkte markiert werden.

Step3. Tritt keine neue Marke auf:

Sind alle Punkte markiert, so ist der Graph G azyklisch.

Gibt es nicht markierte Punkte, so enthält der Graph G einen Zyklus.

Beispiel:

 

 

 

 

 

 

 

 

Azyklisch da alle Punkte markiert sind: 5+ 4+ 3+ 2+ 1+

 

 

 

 

 

 

 

 

 

nicht azyklixh, da nicht alle Punkte markiert sind: 4+

 

Weiterer Algorithmus für dieses Problem:

Streichen von Kanten, die in keinem Zyklus liegen. Kanten <x,y> mit d+(y) =0.

Step1: Kante <x,y> mit d+(y) = 0 wird gestrichen, solange noch Kanten gestrichen werden können.

Step 2: Es kann keine Kante mehr gestrichen werden:

a) keine Kante mehr vorhanden -> G ist azyklisch

b) es gibt noch Kanten -> G ist nicht azyklisch

 

Beispiel:

 

 

			5

 

 

 

 

 

 

 

 

 

 

azyklisch, da alle Kanten gestrichen sind;

 

 

1.3   Algorithmus zur Bestimmung der Komponenten des starken Zusammenhangs

x_o fest ausgewählt:

+ Markierung bekommen jene Knoten, die von x₀ aus erreichbar sind

Markierung bekommen jene Knoten, von dennen x₀ aus erreichbar ist

Step1: x₀ beliebig auswählen (Komponente von x₀ wird bestimmt)

x₀ wird mit + und –  markiert

IND:= 0 (=Indikator, soll angeben, ob überhaupt in einem Durchlauf ein Knoten markiert worden ist)

Step2: Für alle x e V(X) wird untersucht, ob überhaupt ein Nachfolger – oder Vorgänger makiert worden ist.

Wir durchlaufen alle Kanten <x,y>:

a)     x wird + markiert. Ist y nicht mit + markiert, dann wird y mit + markiert, IND := 1.

b)     y wird mit – markeirt. Ist x nicht mit – markiert, dann wird x mit – markiert, IND:=1.

Step3:

Ist IND = 1, so IND:=0 and goto Step2.

Ist IND = 0, dann gehören zur Komponente von X genau jene Knoten, die mit + und mit – markiert sind.

Komponentennummer 1

Zur Bestimmung der übrigen Komponenten werden neue x₀ –Algorithmen durchgeführt. Sind beim 1. Durchlauf alle Knoten mit + oder – markiert, dann ist der Graph G stark zusammenhängend.

 

1.4  Algorithmus zur Bestimmung des reduzierten Graphen

zunächst ein Algorithmus zur Bestimmung der Komponentennummer (KNR). KNR von x ist k(x).

V(G_R) = {K1, ….Kr}

Bestimmung dr Knaten von GR.

Wir durchlaufen alle kanten <x,y> des Grqphen G.

Ist k(x) = k(y) -> nächste Kante untersuchen.

Ist k(x) ¹ k(y) -> <K_k(x), K_k(y)> e E(G_R)

Netzwerke:

G = (V,E) gerichter, ungerichtete oder gemischte Graphen mit Kantenbewertungen.

b(<x,y>) = b(x,y)eR⁺

z.B. : Straßennetz : b(x,y) = Länge der Strecke <x,y>

oder Telefonnetz: b(x,y)= Kosten des Baus der „Strecke“  <x,y> (richtungsunabhängig)

typische Problemstellung zum Beispiel: kürzester Weg zwischen zwei Knoten a und b

 

1.5  Algorithmus zur Bestimmung des kürzesten Weges von einem Startknoten a zu allen übrigen Knoten x (MOORE)

G zusammenhängend, wenn mehrere kürzeste Wege zwischen a und b existieren, so wählen wir einen aus. Wenn eine Bahn existiert, so gibt es eine kürzeste. Der Algorithmus liefert eine kürzeste kantenfolge von a nach b.

Voraussetzung.

Es gibt keinen Zyklus mit negativer Bewertung (Bewertung eines Zyklus = S der Bewertung der Kanten) dies ist sicher erfüllt wenn b(x,y) eR+)

l(x) = die Länge des bisher gefundenen kürzesten Weges (am Ende: Länge des kürzesten Weges von a nach x)

V(x) = Vorgänger auf diesem Weg

s(x) =  Anzahl der Kanten in dem bisher kantenreichsten Weg

Step1: Anzs:= 0, l(a) := 0, V(a):=0, s(a):=0 für x ¹ a: l(x) := ¥, V(x) := ¥, s(x):= ¥

Step2: IND:= 0, Durchlaufen aller Punkte x des Graphen

2a) Ist s(x) = Anzs, so durchlaufen wir alle Kanten <x,y>.

2aa) Ist l(y) =< l(x) + b(x,y),

der bisher gefundene Weg ist nicht schlechter als der neue, goto Step2a

2ab) Ist l(x) > l(x) + b(x,y), dann wird

l(y):= l(x) + b(x,y),

V(y) := x

s(y) := Anzs +1

IND := 1, goto Step 2a

2b) Ist IND = 0, dann Ende erreicht.

l(b) = Abstand von a nach b = d(a,b).

Ist IND = 1, dann ist Anzs:= Anzs + 1, gogo Step 2

 

Typische Problemstellung zum 2. Beispiel . Legen von Leitungen mit minimalen Gesmtkosten. Jeder Knoten ist mit jedem verbunden. Vorraussetzung. G ist zusammenhängend, gesuchter Teilgraph = spanndender Baum mit minimaler Bewertung, B(T) =

 

 

1.6  Algorithmus zur bestimmung des minimalsten spannen den Baums (Algorithmus von Kruskal)

Step1: mark(x) = 0 für alle x e V(G), KNR:=0

Step2. kanten nach Bewertung aufsteigend sortieren

Step3: Durchlaufen der Kanten in dieser Reihenfolge <x,y>

Fall 1:) mark(x) = mark(y)

1a) mark(x) = 0, KNR:= KNR+1

     mark(x) := mark(y) := KNR, <x,y> e E(T)

1b) mark(x) ¹ 0 (Kante erzeugt Kreis) goto next Kante

Fall 2: mark(x) ¹ mark(y)

2a) mark(x) = 0, so <x,y > e E(T) und mark(x):= mark(y)

2b) mark(y) = 0, so <x,y > e E(T) und mark(y):= mark(x)

2a) mark(x) ¹ 0 und mark(y) ¹ 0, so wird <x,y > e E(T) bei allen z mit mark(z) = mark(y) wird mark(z):= mark(x)

Step 4: minimales Gerüst gefunden; ist G nicht zusammenhängend, so ist das minimale Gerüst ein Wald und die verschiedenen Komponenten sind durch verschiedene Werte von mark(x) gekennzeichnet.

 

Exzentrizität klären und bei Beispiel dazuschreiben

was ist d+ bei der def. des 2. Algorithmus bzw. der Azyklizität