Hamiltonkreis, Artikulationspunkt an 2 Graphen zeigen

Question

Aufgabe:

Gegeben seien die beiden Graphen \( A \) und \( B \):

a) Entscheiden Sie, welcher der beiden Graphen \( A \) und \( B \) einen Hamiltonkreis besitzt. Geben Sie den entsprechenden Hamiltonkreis an, oder beweisen Sie, dass keiner exisitiert.

b) Zeigen Sie: Hat ein Graph einen Artikulationspunkt, also einen Knoten \( v \) so dass der Graph nach dem entfernen von \( v \) nicht mehr zusammenhängend ist, so hat der Graph keinen Hamiltonkreis.

c) Zeigen Sie allgemein: Zerfallt ein Graph nach dem Entfernen von \( k \) Knoten in mindestens \( k+1 \mathrm{Zu} \) sammenhangskomponenten, so enthält der Graph keinen Hamiltonkreis.

Answer 1

a)Graph B hat den Hamiltonkreis und A nicht

b&c gleichen Ansatz)

du musst zeigen dass wenn wir nach Def. von Hamiltonkreis alle Knoten einmal besuchen und den selben Knoten beginnen und enden müssen, dann beim löschen von v wird G zu mind. zwei zhk. zerlegt also kann man nicht von dem ersten zu dem zweiten zusammen hängenden Komponenten in G weiter besuchen bzw. wieder zum Anfangspunk zu erreichen. (wenn wir die Brücke zwischen 2 zhk. löschen, dann können wir nicht von einer der zhk. anfangen und wieder zum selben zhk. in G zurückkehren.

sorry für meine schlechte Sprache aber ich habe morgen die Klausur und kenne ich mich aus mit Mathe