Nr. 1
(a)
In Problem 3 beweisen wir, dass der MST eines Graphen eindeutig ist, fals es zu
jedem Schnitt im Graphen eine eindeutige leichte Kante gibt, die diesen Schnitt
kreuzt. Da in Problem 1 die Kostenfunktion injektiv ist, ist JEDES
Kantengewicht eindeutig, damit gelten insbesondere auch die Bedingungen aus
Problem 3 => MST ist eindeutig!
Zu zeigen ist nun, dass jede lokal minimale Kante zu einem MST von G gehoert.
Dazu betrachten wir den Knoten k mit dem eine lokal minimale Kante inzidiert.
Nach der Faerbungsmethode von Tarjan koennen wir als ersten Faerbeschritt die
"Gruene Regel" anwenden mit dem Schnitt ({k}, G\ {k}).
Offensichtlich faerben wir dadurch die lokal minimale Kante die mit k inzidiert
gruen, damit gehoert sie zu einem MST von G.
Da wir so fuer jede lokal minimale Kante argumentieren koennen folgt:
=> Jede lokal minimale Kante gehoert zu einem MST
=> (wegen Eindeutigkeit) Jede lokal minimale Kante gehoert zu allen MST von G
(b)
Widerspruchsbeweis: Angenommen eine Menge lokal minimaler Kanten eines Graphen
habe einen Zyklus Seien die Knoten die den Zyklus bilden k_1, k_2...k_n und die
Gewichte der durch den jeweiligen Knoten induzierten lokal minimalen Kante w_1,
w_2...w_n. Da w_i jedoch k_i und k_i+1 verbindet muss, da die lokal minimale
Kante von k_i+1 nicht (k_i+1, k_i) sondern (k_i+1, k_i+2) ist, muss w_i+1 < w_i
gelten.
Dann haben wir jedoch: w_1 > w_2 > ... > w_n > w_1, Widerspruch! w_1 > w_1 ist
nie wahr.
Also ist die Menge aller lokal minimaler Kanten eines Graphen ein Wald.
(c)
BORUVKA-PHASE
INPUT: einfacher, ungerichteter zusammenhaengender Graph G = (V, E) mit
injektiver Kostenfunktion
w : E -> N+
Die Kanten seien in einem Array uebergeben: E[1...m] wobei in E[i] das
durch E[i] verbundene Knotenpaar stehen soll, also E[i] := {k1, k2}
OUTPUT: Graph Gstrich = (V, E) der durch Kontraktion enstanden ist
Transformiere G in Knoten mit Adjazenzlisten, wobei die kantenID der Wert an \
dem sich die Kante im Array E befindet sei. KnotenID sei die \
Knotennummer /*Dies geht in O(n+m) was in O(m) liegt da n in O(m)
ist.*/
list<Knoten> A; //Liste ueber alle Knoten
class Knoten {
long KnotenID;
list<KnotenGewichtPaar> kanten; /*eine Liste aller Kanten die von diesem
*Knoten ausgehen, es wird ein Zeiger auf
*den Partnerknoten und das Gewicht
*gespeichert*/
list<Knoten::iterator> zusammenhangsKnoten; /*enthalte zu Anfang den
*Iterator in A der auf this zeigt*/
};
class KnotenGewichtPaar {
long kantenID;
list<Knoten>::iterator knoten; //iterator ueber A der auf einen Knoten zeigt
Gewicht gewicht; //Das Gewicht dieser Kante
};
//Schritt (1)
Fuer alle Knoten k in A {
Finde das KnotenGewichtPaar kgp mit niedrigstem Gewicht in k.kanten
list<Knoten::iterator> zusammenhangDesPartnerKnotens = \
kgp.knoten.zusammenhangsKnoten;
Fuege an kgp.knoten.zusammenhangsKnoten k.zusammenhangsKnoten an
Fuege an k.zusammenhangsKnoten zusammenhangDesPartnerKnotens an
/*Wir loeschen die Kante von k zum direkten Verbundspartner, und die Kante die
*zurueck "zeigt"*/
Loesche kgp aus k.kanten
Loesche das KnotenGewichtPaar kgpstrich in kgp.knoten.kanten mit \
&(*kgpstrich.knoten) == &k
}
/*
Schritt (1) liegt in O(m), da wir fuer jeden Knoten alle von ihm ausgehenden
Kanten "abklappern", dabei werden O(m) vergleiche (genauer 2*m Vergleiche...)
ausgefuehrt.
Es sind nun fuer alle Knoten die durch lokal minimale Kanten verbundenen
Zusammenhangskomponenten gefunden, und jeder Knoten eines solchen
Verbundes kennt alle Partnerknoten.
Ausserdem sind die Kanten innerhalb der Zusammenhangskomponenten geloescht
worden.
*/
//Schritt (2)
list<Knoten> Astrich; /*hier kommen die neuen Knoten die durch die Verschmelzung
*entstehen hinein */
list<Knoten>::iterator KnotenIteratorTranslationTable[1...n];
Fuer alle Knoten k in A { /*Wobei A jedoch stetig schrumpft, innerhalb der
*Schleife geloeschte k sind nicht zu iterieren*/
Knoten neuerKnoten; //(1)
list<Knoten>::iterator einfuegePosition = Astrich.push(neuerKnoten); //(2)
einfuegePosition->zusammenhangsKnoten := { einfuegePosition } /*der neue
*Knoten haengt nur mit sich selbst zusammen (3)*/
Fuer alle list Knoten::iterator kiter in k.zusammenhangsKnoten {
Fuege an neuerKnoten.kanten kiter->kanten an //(4)
//Wir speichern den neuen Iterator zur KnotenID
KnotenIteratorTranslationTable[kiter->KnotenID] = einfuegePosition; //(5)
Loesche *kiter aus A //(6)
}
}
//A ist nun leer
A = Astrich
//Wir setzen nun die Iteratoren die auf den Nachbarknoten zeigen richtig
//Ausserdem wird die KnotenID neu gesetzt
long neueKnotenID = 1;
Fuer alle Knoten k in A
k.KnotenID = neueKnotenID++;
Fuer alle KnotenGewichtPaar kgp in k.kanten
kgp.knoten = KnotenIteratorTranslationTable[kgp.knoten->KnotenID]; //(7)
}
LOESCHETEUREMEHRFACHKANTEN(G = ({1...sizeof(A)}, KantenAusAdjazenzlisten(A))
//KantenAusAdjazenzlisten geht in O(m)
return G = ({1...sizeof(A)}, KantenAusAdjazenzlisten(A)), w : E -> N+ (w auch
aus A)
/*
Schritt (2) liegt auch in O(m), die mit (1), (2) und (3) gekenntzeichnete
Zeilen laufen alle nur einmal pro Zusammenhangskomponente, die mit (4), (5) und
(6) laufen nur einmal pro Knoten ab, damit liegt die gesammte Schleife in O(n)
also auch in O(m). Die zweite interessante Stelle bei (7) laeuft ueber die
Kanten des neuen Graphen (nach Verschmelzung), ist also in O(m_neu), da
m_neu < m ist gilt jedoch auch O(m).
*/
Laufzeitanalyse BORUVKA-PHASE:
Sowohl Schritt (1) also auch Schritt zwei sind in O(m) also ist BORUVKA-PHASE in
O(m)
(d)
Da die Kostenfunktion als injektiv und der Graph als zusammenhaengend
vorausgesetzt wird, kann man mit Sicherheit
zu jedem Knoten eine zugehoerige lokal minimale Kante finden. Dies fuehrt jedoch
nach dem Algorithmus der
BORUVKA-PHASE dazu, dass jeder Knoten mindestens mit einem weiteren Knoten
vereinigt wird
=> Nach Ablauf der BORUVKA-PHASE hat sich die Knotenanzahl mindestens halbiert.
(e)
BORUVKA MST:
INPUT: G(V, E), w : E -> N+
OUTPUT: T(V, E) Graph MST von G
T <- leerer Graph
Fuer alle Knoten k in V {
T.E = T.E vereinigt {lokal_minimale_Kante_die_mit_k_inzidiert}
//die Kante kann via kantenID zum Ursprungsgraph zugeordnet werden
}
Gstrich = BORUVKA-PHASE(G)
Wenn in Gstrich nurnoch ein Knoten vorhanden ist:
return T
Sonst
Tstrich = BORUVKA-MST(Gstrich)
return T + Tstrich
Sei mit T(n, m) die Laufzeit von BORUVKA MST mit einem Graph mit n Knoten und m
Kanten gemeint, nach (d) gilt:
T(n, m) <= T(n/2, m) + f(m) //f(m) in O(m)
T(n, m) wird also log(n) mal aufgerufen, und jedes Mal wird ein Aufwand der in
O(m) liegt getaetigt.
Es folgt also das BORUVKA-MST in O(m*log(n)) liegt.