Hausaufgaben vom 15.11.06

(zum 22.11.2006)

1. Alle Punkte eines Graphen haben Grad 3. Zeige, dass der Graph ein Zyklus hat.
   
   
   
2. Jedes Paar von 101 Städten eines Landes sei direkt durch eine Strasse verbunden. Wie viele Strassen kann man gleichzeitig
   reparieren, so dass alle Städte erreichbar bleiben?
   
   
3. Zwischen je zwei Städte eines Landes gibt es eine direkte Einbahnstrasse, die sie verbindet. Zeige, dass man die
   Fahrtrichtung auf einer Strasse ändern kann, so dass alle Städte aus jeder Stadt erreichbar sind.