Musterlösung Blatt 9

H-34: 
Format: discovery time d[v] und finishing time f[v] als 
d[v] | f[v]. Baumkanten sind durchgehend, alle anderen gepunktet
und mit Markierung versehen: R = rückwärts, V ´vorwärts, Q ´quer.

H-35: In einer Variablen g[v] wird der Eingangsgrad des Knotens v
gespeichert. Ausserdem halten wir eine dynamische Menge M und eine
Liste L.

- Initialisiere zunächst g[v]=0 für alle v,
  und M = L = leer.  
- Für jedes v in V
    für jedes u in Adj[v]
      g[v] = g[v] + 1
- Für jedes v in V
    falls g[V] = 0 ist, füge v in M ein
- Solange M nicht leer ist
    nimm ein Element v aus M
    für alle u in Adj[v]
       g[u] = g[u]-1
       falls g[u]=0 ist, füge u in M ein
    entferne v aus M 
    hänge v an L an 

Am Ende enthält L alle Knoten topologisch sortiert. 

Komplexität: Initialisierung braucht O(|V|), erste Schleife O(|E|),
zweite Schleife O(|V|), und die Hauptschleife wieder O(|E|) Schritte,
also insgesamt O(|V|+|E|).

H-36:

H-37: 
Seien T1 und T2 minimale Spannbäume mit Gewicht m in einem
Graphen G, und sei Wi =  [wi1,...,wi(n-1)] die sortierte Liste der
Kantengewichte in Ti, für i=1,2. Zu zeigen: W1 = W2.
Modifiziere die Listen W1 und W2 wie folgt:

 Für jedes k von 1 bis n-1 
   Falls w1k = w2j für ein j
      streiche w1k aus W1 und w2j aus W2.

Am Ende bleiben sortierte Listen X = [x1,...,xk] und Y = [y1,...,yk]
für ein k <= n-1, die keine gemeinsamen Elemente haben.  Sei ObdA 
x1 < y1, also x1 < yi für alle i <= k.

Wähle eine Kante in T1 mit Gewicht x1, die nicht in T2 vorkommt. Nach
Konstruktion muss es eine solche geben. Füge diese Kante zu T2 hinzu,
dann schliesst diese einen Zyklus. Die anderen Kanten in diesem Zyklus
haben alle Gewichte aus Y, da sonst schon ein Zyklus in T1 vorhanden
sein müsste. Durch Entfernen einer dieser Kanten, deren Gewicht yj
sei, erhalten wir also wieder einen Spannbaum, aber dessen Gewicht ist
m-yj+x1 < m, im Widerspruch zur Minimalität von T1 und T2.