Hamilton-Graph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Man Zeige:
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. |
Hi, irgendwie komme ich bei dieser Aufgabe nicht weiter.
Wir haben den Hamiltongraph oder kreis wie folgt definiert:
Unter einen Weg in einem Graphen versteht man eine Folge von paarweise verschiedenen Ecken. Dieser heißt geschlossener Weg oder Kreis, wenn darüberhinaus [mm] (x_n, x_1) \in [/mm] E. Ein Kreis, der jede Ecke im Graphen genau einmal enthält, heißt Hamiltonkreis. Ein Graph, der einen Hamiltonkreis besitzt nennt man Hamilton-Graph.
Bemerkung:
Die Kantenmenge eines Graphen kann genau dann in Kreise geteilt werden, wenn jede Ecke geraden Grad besitzt.
So, wie kann ich das jetzt auf diese Aufgabe anwenden? komm da gerade nicht weiter....
Danke schon mal für Hilfe.
Gruß
|
|
| |
|
Hallo jaruleking,
auch hier ist es einfacher, umgekehrt vorzugehen.
Nimm zwei voneinander getrennte Graphen. Beide müssen sozusagen "fast hamiltonsch" sein, will heißen, es muss möglich sein, durch Hinzufügung einer einzigen Kante (pro Graph) jeden der beiden Graphen hamiltonsch zu machen.
Anders gesagt, es muss eine Reihenfolge aller Ecken des Graphen geben, die man wiederholungsfrei durchlaufen kann. Die ggf. nötige Zusatzkante wäre dann die gedachte Verbindung der ersten und der letzten Ecke dieser Anordnung.
Nun darfst Du eine neue Ecke einzeichnen und sie mit beliebig vielen Ecken beider Graphen verbinden.
Kann der so verbundene Graph hamiltonsch sein? Wenn ja: wie? Wenn nein: warum nicht?
Grüße
reverend
|
|
|
| |
|
hmmm,
also diesen beien aufgaben machen mich noch verrückt  .
habe hier mal ein beispiel gefunden:
http://www.schelthoff.fh-aachen.de/diskret/SS06/vorl6t1.pdf
Folie 11.
Dort haben die auch einen Kreis, entfernen dann eine Ecke und sagen dann, dass die zweite Abbildung nicht mehr hamiltonsch ist, weil ja die Verbindung von F zu D fehlt.
Aber wie kann ich diesen Fall jetzt aufs allegmeine beziehen?
|
|
|
| |
|
Hallo,
ich sehe nicht, wie die gefundene Folie Dir weiterhilft.
Du hast sie aber richtig verstanden bzw. interpretiert!
Denn das, was Du da schreibst, steht da ja eigentlich gar nicht. Aber wie gesagt: so ist es richtig.
Was gefällt Dir denn nicht an meinem Vorschlag?
Mal ganz in Worten: Du beginnst an einer geeigneten Ecke im linken Graphen und durchläufst alle übrigen, ohne eine Ecke zweimal zu besuchen. Dann musst Du zum rechten Graphen, das geht aber nur durch die zusätzliche, verbindende Ecke E. Dann durchläufst Du den rechten Graphen, wieder ohne eine Ecke dort zweimal zu besuchen. Nehmen wir an, dass das bis hier alles problemlos möglich gewesen wäre.
Nun aber musst Du noch an Deinen Anfangspunkt im linken Graphen zurück, und das geht wieder nur über E.
Also kommt E zweimal auf Deinem Weg vor, und dieser Weg kann damit kein Hamiltonkreis sein. Da dies für alle Wege gilt, die alle Ecken durchlaufen, ist der Graph aber nicht hamiltonsch.
Auf der anderen Seite kann er nicht anders aussehen, wenn mit Wegfall von E und allen adjazenten Kanten der Graph in zwei Teile zerfallen soll. Du kannst das sogar auf mehr als zwei Teile verallgemeinern, aber für die Aufgabe ist es nicht nötig.
Mir scheint, dass Du gerade ein ziemliches Brett vor dem Kopf hast. Schlaf mal drüber, das überstehen solche Bretter oft nicht gut...
Viel Erfolg weiterhin,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:22 Mo 10.05.2010 | | Autor: | jaruleking |
Ok danke dir für alles.
Ich warte einfach mal bis morgen  .
grüße
|
|
|
| |
|
HI nochmal,
also mit den ganzen Sachen habe ich mir jetzt mal dies hier zusammengebastelt:
Ein Graph G=(V,E) heißt zusammenhängend, wenn man in ihm von jeder Ecke zu jeder anderen(nicht unbedingt sofort) gelangen kann.
D.h: Ein Graph ist zusammenhängend, wenn er nicht in mehrere Teile zerfällt.
Ein Hamiltonkreis in einem Graphen G = (V,E) ist ein Kreis
(Startecke = Endecke), der alle Ecken von V genau einmal durchläuft. Enthält ein Graph einen Hamiltonkreis, so nennt man ihn hamiltonsch. D.h. aber auch, dass ein Hamiltonkreis zusammenhängend ist und somit nicht in mehrere Teile zerfallen kann!
Ein Punkt p ist ein Kritischer Punkt, wenn es ein Punktepaar (x,y) gibt mit [mm] x\not=y [/mm] und [mm] x\not=p [/mm] und [mm] y\not=p, [/mm] das zusammenhängend ist, nach Entfernung des Punkts p und aller unmittelbar dranhängenden Kanten aber nicht mehr zusammenhängend ist.
Sei K die "kritische" Ecke und der Graph soll bei der Entnahme von K in zwei Zusammenhangskomponenten, sagen wir o.B.d.A. in X und Y, zerfallen. Sei A eine Ecke aus X und B eine aus Y.
Ein Kreis der A und B verbindet,würde K jedoch zwei mal berühren, da ja G zusammenhängend sein muss und K ein kritischer Punkt ist, d.h. A und B verbindet. Und dies führt damit zum Widerspruch der Def. für den Hamiltonkreis.
Meinst du, das reicht so jetzt aus? oder fehlt noch irgendwo eine Begründung?
Gruß
|
|
|
| |
|
Hallo,
mein Netz läuft heute nicht (seit heute Morgen 8h jetzt zum ersten Mal!), und morgen früh verschwinde ich bis Sonntag Abend. Mal sehen, ob ich unterwegs besseren Zugang habe oder wenigstens hier bei Rückkehr alles wieder läuft...
Aber es sieht auch nicht so aus, als bräuchte ich noch eine Internetverbindung für diese Aufgabe. Die Lösung sieht gut aus.
Gratulation!
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:01 Fr 14.05.2010 | | Autor: | jaruleking |
Ok danke dir.
Und gute Reise
ciao
|
|
|
|
