Multigraphen – Übungen

1. Welche der folgenden Graphen sind Multigraphen

   Gibt es Eulersche Kantenzüge? Markiere mögliche Start- und Endknoten.

   

2. Königsberger Brückenproblem

   

3. Wohnungsrundgang

   

   Ist es möglich durch die abgebildete Wohnung einen Rundgang zu machen, so dass man jede Tür nur genau einmal passiert?

   Begründe deine Antwort.

4. Briefträgerproblem

   

   Ist es möglich, dass der Briefträger seine Tour bei der Post beginnt, die durchgezogenen Straßen genau einmal abläuft und zum Schluss wieder zur Post zurückkehrt? Was ändert sich, wenn sein Zustellgebiet vergrößert wird und die gestrichelt gezeichneten Straßen hinzukommen?

5. Schneepflug

   Ein Gemeindemitarbeiter muss morgens einige Straßen mit einem Schneepflug räumen. Er startet im Bauhof B, will alle Straßen nur einmal abfahren und dann wieder zum Bauhof zurückkehren.

   

   1. Ist das möglich? Wenn ja, mache einen Vorschlag.
   2. Ist es möglich, wenn die Straße von E nach H wegen eines Unfalls gesperrt ist?

Multigraphen – Übungen: Herunterladen [odt][186 KB]

Multigraphen – Übungen: Herunterladen [pdf][151 KB]

Weiter zu andere Reihenfolge