(Teil{)Musterlosung zum 12.Aufgabenblatt (Regina Richter) 1. Hamiltonsche Kreise (a) Seien N ,M die beiden disjunkten Knotenmengen des Kn;m , j j= N n und j j= M . m : Der vollstandige bipartite Graph Kn;m ist genau dann ein Baum, wenn = 1 oder m = 1. Beweis: Wenn n = 1 und m > 1, dann ist der Knoten aus N unser einziger innerer Knoten und die Knoten aus M sind die Blatter. Der K1;1 ist trivialerweise ein Baum, denn er besteht aus genau einer Kante. Wenn n; m 2, dann ist der vollstandige K2;2 Untergraph des Graphen und dieser ist ein Kreis, d.h., der Graph kann kein Baum sein. Behauptung n Der vollstandige bipartite Graph Kn;m besitzt einen Hamiltonschen Kreis, genau dann wenn n = m > 1. Die Anzahl der verschiedenen Hamiltonschen Kreise des Kn;n ist n!(n 1)! Behauptung: Beweis: Wenn n > m ist, dann kann der Graph keinen Hamiltonschen Kreis besitzen, denn dieser besucht die Knoten aus N und M abwechselnd und jeden genau einmal, also muss n = m sein. n = m = 1 scheidet aus, denn das ist ein Baum. Wir legen o.B.d.A. fest, dass wir unseren Hamiltonschen Kreis in der Menge N starten wollen. Fur den Anfangsknoten gibt es n Moglichkeiten. Den Kreis mussen wir in M fortsetzen; dafur haben wir n Fortsetzungsmoglichkeiten. Danach haben wir noch n 1 Moglichkeiten, den Kreis mit einem Knoten aus N fortzusetzen. In M ist auch schon einer verbraucht, also n 1 Moglichkeiten fur den nachsten Knoten aus M . In N sind schon 2 Knoten verbraucht, also n 2 Moglichkeiten unseren Kreis fortzusetzen. Genauso wie in M . Dies setzen wir fort, bis wir alle Knoten erreicht haben. Die Anzahl aller moglichen Kreise mit einem Startknoten in N ist also: n ( n n 1) (n 1) (n 2) (n 2) : : : 1 1 = n! n! (1) Nun gibt es aber zyklische Vertauschungen. Wenn wir einen von den oben konstruierten Hamiltonschen Kreisen betrachten, dann bemerken wir, dass wir an n verschiedenen Knoten anfangen konnen und den gleichen Hamiltonschen Kreis erhalten, da n Knoten in unserer Startmenge N sind. Jeder Kreis wurde also n-mal gezahlt. Die Anzahl der (echt verschiedenen) Hamiltonschen Kreise ist demnach: ! n! n n = (n 1)! n! (2) Diese Aufgabe wurde ubrigens schon einmal gelost, s. Musterlosung zu Ubung 6, Aufgabe 7b. Hinweis: Was wir soeben abgezahlt haben, sind eigentlich die gerichteten Hamiltonkreise. Will man die ungerichteten zahlen, so muss man jeweils die 2 zueinander inversen identizieren und dann sind es (n 1)! n!=2 viele. 2. B aume und k urzeste Wege (a) Sei i die Anzahl der inneren Knoten und l die Anzahl der Blatter in dem q {naren Baum. Es gibt insgesamt n 1 (gerichtete) Kanten. Da von jedem inneren Knoten genau q Kanten abgehen, ist n 1 = i q . Also i = 1 n (3) q Da jeder Knoten entweder innerer Knoten oder Blatt ist, haben wir l =n i =n 1 n q (4) (b) Was ist die Anzahl der Kanten in einem Wald mit n Knoten? Sei c die Anzahl der Baume im Wald F und ni mit 1 i c die Anzahl der Knoten im i{ten Baum. Dieser hat dann ni 1 Kanten. Insgesamt haben wir ci=1 (ni 1) = n c viele Kanten. Diese Anzahl wird minimal fur c = n, d.h., jeder Baum im Wald besteht nur aus einem Knoten und es gibt keine Kanten. Die Kantenzahl wird maximiert fur c = 1, der Wald besteht aus genau einem Baum mit n Knoten. (c) Mit dem Algorithmus BFS (Breitensuche) mit Start in Knoten a berechnen wir kurzeste Wege zu allen anderen Knoten im Graphen. Die Existenz solcher Wege ist wegen des Zusammenhangs des Graphen gewahrleistet. Um einen kurzesten Pfad von Knoten x zu Knoten y uber a zu konstruieren, konkatenieren wir den inversen Weg zum berechneten kurzesten Weg von a nach x mit dem berechneten kurzesten Weg von a nach y . Das dies ein tatsachlich kurzester Pfad von x nach y uber a ist, ist klar. Denn falls es noch einen kurzeren gabe, so ware dieser auf dem Teilstuck von x nach a oder auf dem Teilstuck von a nach y kurzer. Widerspruch, denn BFS berechnet korrekt kurzeste Wege! P 3. Totale Senke Ein totale Senke in einem gerichteten Graphen (ohne Schleifen) G = (V ; E ) ist ein Knoten mit Ingrad jV j 1 und Ausgrad 0. Der Graph sei in Adjazenzmatrixdarstellung (mit jV j2 Eintragen) gegeben. Argumentieren Sie, dass man nur linear in jV j viele Anfragen an Matrixeintrage stellen muss, um zu entscheiden, ob G eine totale Senke besitzt. : Seien v1 ; : : : ; vn die Knoten des Graphen. Man beachte, dass es hochstens eine totale Senke vc im Graphen geben kann. Was lernt man aus dem Eintrag ai;j in der Adjazenzmatrix fur i 6= j ? Falls ai;j = 0, so kann vj keine totale Senke sein, denn es gibt keine Kante von vi nach vj ; falls ai;j = 1 so entfallt vi als Kandidat fur eine totale Senke. L osung In einer ersten Phase werden wir sequentiell aus den Knoten v1 ; : : : vn einen einzigen Kandidaten vc bestimmen, der als totale Senke in Frage kommt. Angenommen, v1 ; : : : ; vc 1 scheiden als Kandidaten schon aus und vc ist der aktuelle zu untersuchende Knoten: (a) Falls ein minimales j mit c < j und ac;j = 1 existiert, wissen wir nunmehr, dass v1 ; : : : ; vc ; : : : vj 1 als totale Senke nicht in Frage kommen. Wir setzen c = j und fahren f ur c < n rekursiv fort bzw. falls c = n gilt, erkl aren wir vn zum einzigen Kandidaten. (b) Andererseits, falls es ein solches j nicht gibt, wird das aktuelle vc als einziger Kandidat ausgegeben. Man beachte, dass in dieser Phase genau n 1 Anfragen an die Adjazenzmatrix gestellt wurden. Nun ist noch zu uberprufen, ob der einzige Kandidat vc tatsachlich totale Senke ist. Dazu wird getestet, ob ac;k = 0 fur alle k 6= c und auerdem ai;c = 1 fur alle i 6= c gilt. In dieser zweiten Phase werden also hochstens 2n 2 Matrixeintrage getestet. Insgesamt kann man damit die Frage nach der Existenz einer totalen Senke mit 3n 3 Anfragen an die Adjzenzmatrix beantworten und diese Senke auch nden, falls sie existiert.