Beweis: Hamiltonschen Kreis < Topologie+Geometrie < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Ein zusammenhängender Graph, ohne Schlinge und Mehrfachkanten, mit n>2 Ecken und y(E) [mm] \ge \bruch{1}{2} [/mm] * n für jede Ecke E besitzt einen Hamiltonschen Kreis.
BEWEIS:
In dem gegebenen Graphen G führen wir neue Ecken ein, die sämtlich mit allen Ecken von G verbunden werden. Dabei sei k die kleinste Anzahl von Ecken, die notwendig ist, um im entstehenden Graphen G´einen Hamiltonschen Kreis zu erhalten.
Besitzt G n Ecken, dann kann man z.B. durch Hinzufügen von n weiteren Ecken in jedem Fall auf diese Weise einen Graphen G´mit einem Hamiltonschen Kreis erzeugen.
Wir nehmen nun k > 0 an und werden einen Widerspruch herleiten. Sei
A [mm] \to [/mm] B [mm] \to [/mm] C [mm] \to [/mm] .... [mm] \to [/mm] A
ein Hamiltonscher Kreis von G´, wobei A und C Ecken von G sind und B eine der neuen Ecken. Dann kann A nicht zu C in G benachbart sein, andernfalls könnten wir B weglassen im Widerspruch zu Minimalität von k. Dabei heißen zwei Ecken benachbart, wenn sie durch eine Kante verbunden sind. Ferner kann eine zu C benachtbarte Ecke C´ nicht unmittelbar auf eine zu A benachbarte Ecke A´folgen, da wir sonst
A [mm] \to [/mm] B [mm] \to [/mm] C.... [mm] \to A´\to C´\to [/mm] .... [mm] \to [/mm] A
ersetzen können durch
A [mm] \to [/mm] A´ [mm] \to [/mm] ..... [mm] \to [/mm] C [mm] \to C´\to..... \to [/mm] A,
indem wir den zwischen C und A´gelegenen Teil des Hamiltonschen Kreises umkehren. Weil dann B fehlt, wäre k ebenfalls nicht minimal. Also istdie Anzahl der nicht zu C benachtbarten Ecken, d.h. mindestens [mm] \bruch{1}{2} [/mm] * n +k. Natürlich ist die Anzahl der zu C benachtbarten Ecken von G´auch mindestens [mm] \bruch{1}{2} [/mm] *n+k . Da keine Ecke von G´gleichzeitig zu C benachbart und nicht benachtbart sein kann, ist folglich die Gesamtzahl der Ecken von G´mindestens gleich n+2*k, womit wir einen widerspruch erziehlt haben. |
Hi also, ich komme mit bis zum Widerspruch der minimalität von k.
Wenn B hinzugefügt wurde, dann konnte keine verbindung zwischen A und C zustanden gekommen sein.
Die Frage die ich mir hier stelle:
1) Wieso ist die Minimalität dann nicht gegeben, weil k dann =0 ist?
2) Ich verstehe nun nicht ganz mit den Einfügen von C´usw.
3) Am Ende wird dann festgelegt das n+2*k gilt, ist dies richtig und das obrige y(E) [mm] \ge \bruch{1}{2} [/mm] * n gilt nicht?
Währe super nett wenn ihr mir helfen könntet!
Ich hoffe es ist zu erkennen das A´etc. hier im Forum was dicker Stehen, hat den ´irgendwie nicht gemacht
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Mo 18.05.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
