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

Übungsaufgaben

Aufgabe Referenznummer erstellen

Zeige, dass der vollständige Graph ${}K_{n}$ mit ${}n\geq 3$ 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 ${}G$ 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 ${}4\times 4$-Brett. Ist es möglich, durch eine Zugfolge mit dem Springer alle Felder genau einmal zu treffen?

Aufgabe Referenznummer erstellen

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

Aufgabe Referenznummer erstellen

Zeige, dass im Satz von Ore die Bedingung ${}{\#\left(V\right)}\geq 3$ 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 ${}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.