Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 22/kontrolle
- Übungsaufgaben
Aufgabe Referenznummer erstellen
Zeige, dass der vollständige Graph mit hamiltonsch ist.
Aufgabe Referenznummer erstellen
Begründe, dass der abgebildete Graph hamiltonsch ist.
Aufgabe Referenznummer erstellen
Zeige, dass ein Graph genau dann hamiltonsch ist, wenn es einen knotenbijektiven Graphhomomorphismus von einem Rundgang nach gibt.
Aufgabe * Referenznummer erstellen
Zeige, dass ein Graph genau dann hamiltonsch ist, wenn sein Umfang mit seiner Knotenanzahl übereinstimmt.
Aufgabe * Referenznummer erstellen
Wir betrachten die Züge des Springers im Schach auf einem -Brett. Ist es möglich, durch eine Zugfolge mit dem Springer alle Felder genau einmal zu treffen?
Aufgabe Referenznummer erstellen
Es sei ein Rundgang. Charakterisiere die Äquivalenzrelationen auf mit der Eigenschaft, dass der Quotientengraph hamiltonsch ist.
Aufgabe Referenznummer erstellen
Zeige, dass im Satz von Ore die Bedingung notwendig ist
- Aufgaben zum Abgeben
Aufgabe (3 Punkte)Referenznummer erstellen
Bestimme die Paarungszahl in einem hamiltonschen Graphen.
Aufgabe (3 (1+1+1) Punkte)Referenznummer erstellen
Es sei der abgebildete Graph.
- Überprüfe die numerische Bedingung aus dem Satz von Ore für jedes Punktepaar von .
- Ist hamiltonsch?
- Zeige, dass der Graph hamiltonsch wird, sobald man eine beliebige Kante hinzutut.