Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 22

Übungsaufgaben

Aufgabe

Zeige, dass der vollständige Graph ${}K_{n}$ mit ${}n\geq 3$ hamiltonsch ist.

Aufgabe

Begründe, dass der abgebildete Graph hamiltonsch ist.

Aufgabe

Zeige, dass ein Graph genau dann hamiltonsch ist, wenn es einen knotenbijektiven Graphhomomorphismus von einem Rundgang nach ${}G$ gibt.

Aufgabe *

Zeige, dass ein Graph genau dann hamiltonsch ist, wenn sein Umfang mit seiner Knotenanzahl übereinstimmt.

Aufgabe *

Wir betrachten die Züge des Springers im Schach auf einem ${}4\times 4$-Brett. Ist es möglich, durch eine Zugfolge mit dem Springer alle Felder genau einmal zu treffen?

Aufgabe

Es sei ${}H$ ein Rundgang. Charakterisiere die Äquivalenzrelationen ${}\sim$ auf ${}H$ mit der Eigenschaft, dass der Quotientengraph ${}G=H/\sim$ hamiltonsch ist.

Aufgabe

Zeige, dass im Satz von Ore die Bedingung ${}{\#\left(V\right)}\geq 3$ notwendig ist

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Bestimme die Paarungszahl in einem hamiltonschen Graphen.

Aufgabe (3 (1+1+1) Punkte)

Es sei ${}G$ der abgebildete Graph.

1. Überprüfe die numerische Bedingung aus dem Satz von Ore für jedes Punktepaar von ${}G$.
2. Ist ${}G$ hamiltonsch?
3. Zeige, dass der Graph hamiltonsch wird, sobald man eine beliebige Kante hinzutut.