Hamiltonscher Graph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Folgende Behauptung ist zu beweisen: Kann der Zusammenhang eines Graphen G durch die Entnahme einer einzigen Ecke und sämtlicher mit dieser Ecke inzidierender Kanten zerstört werden, so ist G kein Hamiltonscher Graph. |
Hallo,
unter den inzidierenden Kanten versteht man alle mit dieser Ecke verbundenen Kanten, oder?
Bei Wikipedia habe ich gefunden: "Ein Graph heißt hamiltonsch, falls er einen Hamiltonkreis besitzt. Ein Hamiltonkreis ist ein Kreis, der alle Knoten des Graphen enthält."
Das mit dem Hamiltonkreis ist mir nicht ganz klar. Wie soll man das denn beweisen? Unser Assistent meinte, der Beweis wäre nur eine Zeile. Kann mir jemand den Beweis geben?
Vielen Dank!
(Ich habe diese Frage nirgendwo sonst gestellt.)
|
|
| |
|
Hallo MasterEd!
> Folgende Behauptung ist zu beweisen: Kann der Zusammenhang
> eines Graphen G durch die Entnahme einer einzigen Ecke und
> sämtlicher mit dieser Ecke inzidierender Kanten zerstört
> werden, so ist G kein Hamiltonscher Graph.
> Hallo,
>
> unter den inzidierenden Kanten versteht man alle mit dieser
> Ecke verbundenen Kanten, oder?
Ja.
> Bei Wikipedia habe ich gefunden: "Ein Graph heißt
> hamiltonsch, falls er einen Hamiltonkreis besitzt. Ein
> Hamiltonkreis ist ein Kreis, der alle Knoten des Graphen
> enthält."
>
> Das mit dem Hamiltonkreis ist mir nicht ganz klar. Wie soll
> man das denn beweisen? Unser Assistent meinte, der Beweis
> wäre nur eine Zeile. Kann mir jemand den Beweis geben?
Also (einfach) zusammenhängend bedeutet doch, dass ich mehr Zusammenhangskomponenten erhalte, wenn ich einen Knoten entferne, als ich vorher hatte. Wenn ich also hier einen Knoten samt seiner Kanten entferne und dann zwei Zusammenhangskomponenten erhalte (weil der Graph ja vorher zusammenhängend war, gab es ja nur eine Zusammenhangskomponente), dann können diese beiden durch den Knoten, den ich gerade weggenommen habe, ja nur an einer Stelle verbunden worden sein, aber nicht an beiden, also nicht zu einem Kreis verbunden gewesen sein.
Kann ich irgendwie schlecht ausdrücken, aber das ist doch eigentlich klar... Müsste man nur noch vernünftig aufschreiben...
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Mi 30.05.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
