Hamiltonsche Kreise

12.03.2015, 14:12	rene081586	Auf diesen Beitrag antworten »
Hamiltonsche Kreise Meine Frage: Hi, ich habe mit folgender Aufgabe irgendwie Probleme: Zeigen Sie, dass der Petersengraph a) nicht hamiltonsch ist b) hamiltonsch ist, wenn man eine beliebige Ecke entfernt Meine Ideen: G. A. Dirac (1952), der historische Ausgangspunkt der Entdeckung einer ganzen Reihe von Bedingungen: Jeder Graph $\begin{eqnarray} G \end{eqnarray}$ mit Minimalgrad mindestens $\begin{eqnarray} \tfrac{n}{2} \end{eqnarray}$ hat einen Hamiltonkreis. Wobei aber der Minimalgrad beim Petersengraph ja 3 und n=10 ist. somit bei a.) $\begin{eqnarray} min deg(v)=3\leq 5=\frac{10}{2} \end{eqnarray}$ , also nicht hamiltonisch aber bei b.) $\begin{eqnarray} min deg(v)=3\leq 4,5=\frac{19}{2} \end{eqnarray}$ , was ja bedeuten würde, dass er immer noch nicht hamiltonisch ist. Verstehe ich da was falsch? Danke und viele Grüße
12.03.2015, 14:55	Widderchen	Auf diesen Beitrag antworten »
Hallo, Teilaufgabe a) hast du richtig gelöst. Du hast dabei das oben genannte Korollar verwendet. In Teilaufgabe b) verändert sich dein Minimalkgrad durch Entfernen einer Ecke, oder etwa nicht?? Außerdem heißt es $\begin{eqnarray} 4,5 = \frac{9}{2} \end{eqnarray}$ Ein Graph G heißt hamiltonsch, wenn dieser einen Hamiltonkresi enthält. Ein Hamiltonkreis in einem Graphen $\begin{eqnarray} G = (V , E) \end{eqnarray}$ ist ein Kreis (Startknoten = Endknoten), der alle Knoten von $\begin{eqnarray} V \end{eqnarray}$ genau einmal durchläuft. In Teil b) musst du - wenn ich mich nicht irre - folgende Fallunterscheidung betrachten: 1) Entferne eine beliebige Ecke vom äußeren Pentagramm (die anderen Fälle folgen dann aus Symmetriegründen) , z.B. Ecke "0" oder "1" und versuche dann einen Hamiltonkreis zu zeichnen. 2) Suche wie in 1) einen Hamiltonkreis, nachdem du eine der Ecken 3 , 4 , 5 , 6 oder 8 entfernt hast. Auch hier genügt es wie in 1) nur einen Fall zu betrachten, da alle anderen Graphen isomorph zueinander wären. Eine Lösungsskizze zu b), aber auch zu a) findest auch unter dem folgenden Link: http://www.math.uni-leipzig.de/~stolz/LoesungDS07.pdf Viele Grüße Widderchen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »