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

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Übungsaufgaben

Aufgabe

Zeige, dass der vollständige Graph mit hamiltonsch ist.


Aufgabe *

Dürer graph hamiltonicity.svg

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 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 -Brett. Ist es möglich, durch eine Zugfolge mit dem Springer alle Felder genau einmal zu treffen?


Aufgabe

Es sei ein Rundgang. Charakterisiere die Äquivalenzrelationen auf mit der Eigenschaft, dass der Quotientengraph hamiltonsch ist.


Aufgabe

Zeige, dass im Satz von Ore die Bedingung notwendig ist




Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Bestimme die Paarungszahl in einem hamiltonschen Graphen.


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

Undirected graph no background.svg

Es sei der abgebildete Graph.

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



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)