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:
azyklisch, da alle Kanten gestrichen sind;
1.3 Algorithmus zur Bestimmung der Komponenten des starken Zusammenhangs
xo fest ausgewählt:
+ Markierung bekommen jene Knoten, die von x0 aus erreichbar sind
Markierung bekommen jene Knoten, von dennen x0 aus erreichbar ist
Step1: x0 beliebig auswählen (Komponente von x0 wird bestimmt)
x0 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 x0 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(GR) = {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) -> <Kk(x), Kk(y)> e E(GR)
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