Bipartiter Graph und Hamilto. < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Man zeige, dass ein bipartiter Graph mit einer ungeraden Zahl von Ecken nicht Hamiltonsch ist. |
Hi,
auch bei dieser Aufgabe komme ich gerade nicht weiter, bzw. ich weiß nicht mal, wie ich anfangen muss.
deswegen wäre ich über hilfe sehr dankbar.
Grüße
|
|
| |
|
Hallo jaruleking,
nimm einen Graphen mit ungerader Zahl von Ecken, der hamiltonsch ist. Geh dann einen (beliebigen, falls es mehrere gibt) Hamiltonkreis ab und zeige, dass der Graph nicht bipartit sein kann.
Das ist ziemlich einfach. Geh einfach mal alle Kanten der Reihe nach ab und ignoriere alle, die nicht zum Hamiltonkreis gehören.
Außerdem musst Du Dir noch überlegen, ob Du dann wirklich das Gesuchte gezeigt hast.
Grüße
reverend
|
|
|
| |
|
hmmmm,
also du sagst ja, ich soll irgenden einen graphen mit ungeraden Eckenzahl nehmen, also z.B. [mm] K_3 [/mm] oder [mm] K_5 [/mm] oder [mm] k_7, [/mm] etc... und dann daraus zeigen, dass dieser Graph nicht bipartit ist.
Aber die Aufgabenstellung sagt doch, dass wir von einem bipartiten Grapen ausgehen sollen. und die haben dann doch die Form [mm] K_{n,m}. [/mm] in unserem Fall n,m sind ungerade!
irgendwie komme ich da noch nicht weiter....
|
|
|
| |
|
Hallo nochmal,
fangen wir doch mal mit dem zweiten an.
Wenn Du zeigen sollst, dass ein Tier mit vier Beinen kein Rabe sein kann, dann zeigst Du genau dasselbe, wenn Du zeigst, dass ein Rabe keine vier Beine haben kann.
[mm] (A\Rightarrow \overline{B}) \gdw (B\Rightarrow \overline{A})
[/mm]
Und zum ersten: Du sollst nicht irgendeinen Graphen [mm] K_{2n+1} [/mm] nehmen, sondern einen, der hamiltonsch ist, also einen Hamiltonkreis enthält. Und diesen Kreis (bzw. einen davon, wenn es mehrere gibt) schaust Du Dir mal an. Er wird Dir zeigen, dass der Graph nicht bipartit sein kann. Vielleicht hilft es Dir, wenn Du Dir vorstellst, dass es rote und grüne Ecken gibt.
Grüße
reverend
|
|
|
| |
|
Kann ich dann nicht einfach das Haus vom Nikolaus nehmen. Also Haus mit Dach oben.
Dann haben wir nämlich 5 Ecken, der Graph ist hamiltonsch, aber nicht bipartit, wenn ich das gerade richtig sehe, oder?
Würde dieses Beispiel dann schon als Beweis ausreichen?
|
|
|
| |
|
Hallo,
nein, ein Gegenbeispiel reicht nicht. Vielleicht gibt es ja einen anderen Graphen, der ungerader Ordnung, bipartit und hamiltonsch ist?
Dass das nicht sein kann, sollst Du allgemein zeigen.
Ich weiß nicht, wo Du gerade hängst.
Manchmal ist es hilfreich, sich nochmal die Definitionen vorzunehmen: wann ist ein Graph bipartit? Und wann ist er hamiltonsch?
Grüße
reverend
|
|
|
| |
|
Ja aber genau dieses allgemeine zeigen, weiß ich gerade nicht wie das geht.
aus deinem ersten beitrag hatte ich entnommen, dass ich das an einem beispiel zeigen soll. mir war aber auch klar, dass es dann damit nicht allgemein gezeigt ist.
Also zu den Begriffen:
1) Ein Hamiltonkreis ist ein geschlossener Pfad in einem Graphen G = (V,E) (V Menge der Knoten, E Menge der Kanten), der jede Ecke genau einmal enthält. Lässt ein Graph einen Hailtonkreis zu, so nennen wir den Graphen Hamilton-Graph.
2) Ein einfacher Graph G = (V,E) (V Menge der Knoten, E Menge der Kanten) heißt bipartit, falls sich seine Ecken in zwei disjunkte Teilmengen A und B aufteilen lassen, sodass zwischen den Knoten innerhalb beider Teilmengen keine Ecken verlaufen.
So verstehen tu ich diese beidnen Def. eigentlich, dachte ich zumindest. Aber bei der Anwendung auf die Aufgabe haperts jetzt....
|
|
|
| |
|
Na dann...
Aus wievielen Kanten besteht denn ein Hamiltonkreis, der eine ungerade Anzahl von Ecken durchläuft?
Wenn der Graph bipartit ist, dann führt Dein erster Schritt z.B. von Rot nach Grün, und Dein zweiter von Grün nach Rot etc.
Dein letzter Schritt muss wieder auf der Ecke landen, mit der Du begonnen hast. Welche Farbe hat sie also?
An einem Beispiel zu arbeiten, ist schon ok. Nur bringt es Dir nicht die Lösung, vielleicht aber die Einsicht, die für die Verallgemeinerung notwendig ist. Probiers also ruhig mit 3, 5 oder 7 Knoten. Oder 1023, wenn Du Zeit hast.
Viel Erfolg
reverend
|
|
|
| |
|
> Aus wievielen Kanten besteht denn ein Hamiltonkreis, der eine ungerade Anzahl von Ecken durchläuft?
Das müsste doch die Anzahl der Ecken sein, oder? Also bei 5 Ecken z.B., dann auch 5 Kanten.
> Wenn der Graph bipartit ist, dann führt Dein erster Schritt z.B. von Rot nach Grün, und Dein zweiter von Grün nach Rot etc.
> Dein letzter Schritt muss wieder auf der Ecke landen, mit der Du begonnen hast. Welche Farbe hat sie also?
Also sie müsste dann eigentlich Rot haben. Aber ich habe mir auch dies nochmal am Haus vom Nikolaus mit 5 Ecken gemalt. Fangen wir mit rot an. also rot, grün, rot, grün, rot
> An einem Beispiel zu arbeiten, ist schon ok. Nur bringt es Dir nicht die Lösung, vielleicht aber die Einsicht, die für die Verallgemeinerung notwendig ist. Probiers also ruhig mit 3, 5 oder 7 Knoten. Oder 1023, wenn Du Zeit hast.
Die Sache ist ja nur, ich weiß nicht, wie ich gebinnen muss. Macht man das durch Induktion oder wie?
|
|
|
| |
|
Hmpf.
Das ist als Gruß gemeint...
Also fünf Ecken, die erste sei Rot:
1. Schritt: von Rot nach Grün,
2. Schritt: von Grün nach Rot,
3. Schritt: von Rot nach Grün,
4. Schritt: von Grün nach Rot,
5. Schritt: von Rot nach Grün.
Du stehst jetzt wieder auf der Ecke, wo Du losgegangen bist. Als Du losgingst, war die Ecke rot. Jetzt aber ist sie grün.
Nehmen wir an, es handle sich weder um einen Chamäleon- noch um einen Ampelmännchen-Graphen, sondern einen gewöhnlichen bipartiten. Was geschieht dann den zögerlichen Ecken, die sich nicht für eine Farbe entscheiden können? Gibt es die überhaupt, oder dürfen die gar nicht mitspielen?
 reverend
|
|
|
| |
|
> Nehmen wir an, es handle sich weder um einen Chamäleon- noch um einen Ampelmännchen-Graphen, sondern einen gewöhnlichen bipartiten. Was geschieht dann den zögerlichen Ecken, die sich nicht für eine Farbe entscheiden können? Gibt es die überhaupt, oder dürfen die gar nicht mitspielen?
Das habe ich leider nicht so verstandne .
Also ich versuche gerade, das ganze induktiv zu zeigen, aber klappen tus nicht so.
I.A.: sei n=3, da der Fall n=1 nicht existiert.
Für ein 3x3. Denn hier bekomme ich schon heraus, dass der Graph hamiltoisch ist....
|
|
|
| |
|
Hallo nochmal,
>> Nehmen wir an, es handle sich weder um einen Chamäleon-
>> noch um einen Ampelmännchen-Graphen, sondern einen
>> gewöhnlichen bipartiten. Was geschieht dann den
>> zögerlichen Ecken, die sich nicht für eine Farbe
>> entscheiden können? Gibt es die überhaupt, oder dürfen
>> die gar nicht mitspielen?
>
> Das habe ich leider nicht so verstandne .
Eine Ecke kann nicht zugleich rot und grün sein. Der Weg ist also nicht möglich. Und die Formulierung stammte aus dem Bereich "mathematisches Kabarett".
> Also ich versuche gerade, das ganze induktiv zu zeigen,
> aber klappen tus nicht so.
Ginge auch, ist aber nicht nötig.
> I.A.: sei n=3, da der Fall n=1 nicht existiert.
>
> Für ein 3x3. Denn hier bekomme ich schon heraus, dass der
> Graph hamiltoisch ist....
Nicht jeder Dreiergraph ist hamiltonsch! Denk mal drüber nach. Aber wenn er es ist (z.B. ein Dreieck), dann mach ihn mal bipartit. Das wird nicht gehen, wie Du leicht sehen wirst.
Vielleicht ist es einfacher, Du zeigst erstmal eine kleinere Form, nämlich dieses (nicht präzis formulierte!)
Lemma: jeder bipartite Kreis hat eine gerade Zahl von Ecken.
Es gilt nicht nur für Hamiltonkreise, sondern für jeden Kreis in einem bipartiten Graphen.
***
Ein anderer Weg wäre, einen bipartiten Kreis mit einer geraden Zahl von Ecken zu nehmen (der ja einfach zu konstruieren ist), und dann genau eine Ecke so einzufügen, dass der Kreis bipartit bleibt.
Dazu muss eine Kante aufgeschnitten werden. An ihrem einen Ende liegt eine rote Ecke, am anderen eine grüne. Die "neue" Ecke kommt nun dazwischen. Sie darf nicht rot sein, weil sie ja mit einer bestehenden roten verbunden werden soll. Aber sie darf auch nicht grün sein, weil sie mit einer anderen grünen verbunden wird. Andererseits muss sie rot sein, weil sie mit einer grünen Ecke verbunden wird, und sie muss grün sein, weil sie mit einer roten Ecke verbunden wird.
Fazit: es ist nicht möglich, genau eine Ecke in einen bipartiten Kreis einzufügen.
Jetzt wieder Du...
rev
|
|
|
| |
|
> Eine Ecke kann nicht zugleich rot und grün sein. Der Weg ist also nicht möglich. Und die Formulierung stammte aus dem Bereich "mathematisches Kabarett".
achso, ok.
> Vielleicht ist es einfacher, Du zeigst erstmal eine kleinere Form, nämlich dieses (nicht präzis formulierte!)
> Lemma: jeder bipartite Kreis hat eine gerade Zahl von Ecken.
Kann man das nicht einfach so begründen:
Sei G bipartit mit Bipartition A und B der Eckenmenge. Die Ecken jedes Kreises müssen abwechselnd in A und B liegen, weshalb die Länge gerade sein muß.
> Ein anderer Weg wäre, einen bipartiten Kreis mit einer geraden Zahl von Ecken zu nehmen (der ja einfach zu konstruieren ist), und dann genau eine Ecke so einzufügen, dass der Kreis bipartit bleibt.
> Dazu muss eine Kante aufgeschnitten werden. An ihrem einen Ende liegt eine rote Ecke, am anderen eine grüne. Die "neue" Ecke kommt nun dazwischen. Sie darf nicht rot sein, weil sie ja mit einer bestehenden roten verbunden werden soll. Aber sie darf auch nicht grün sein, weil sie mit einer anderen grünen verbunden wird. Andererseits muss sie rot sein, weil sie mit einer grünen Ecke verbunden wird, und sie muss grün sein, weil sie mit einer roten Ecke verbunden wird.
> Fazit: es ist nicht möglich, genau eine Ecke in einen bipartiten Kreis einzufügen.
Die Sache ist. Das was du da oben beschrieben hast. Habe ich so eigentlich verstanden. Aber das ist doch auch nur ein Beispiel, oder??? Damit wäre der Beweis ja nicht für jedes ungerade n gezeigt, oder?
|
|
|
| |
|
Hallo jaruleking,
ah, ein Fortschritt!
> > Vielleicht ist es einfacher, Du zeigst erstmal eine
> > kleinere Form, nämlich dieses (nicht präzis
> > formulierte!)
> > Lemma: jeder bipartite Kreis hat eine gerade Zahl von
> > Ecken.
>
> Kann man das nicht einfach so begründen:
> Sei G bipartit mit Bipartition A und B der Eckenmenge. Die
> Ecken jedes Kreises müssen abwechselnd in A und B liegen,
> weshalb die Länge gerade sein muß.
Ja, genaaaau.
> > Ein anderer Weg wäre, einen bipartiten Kreis mit einer
> geraden Zahl von Ecken zu nehmen (der ja einfach zu
> konstruieren ist), und dann genau eine Ecke so einzufügen,
> dass der Kreis bipartit bleibt.
> > Dazu muss eine Kante aufgeschnitten werden. An ihrem
> einen Ende liegt eine rote Ecke, am anderen eine grüne.
> Die "neue" Ecke kommt nun dazwischen. Sie darf nicht rot
> sein, weil sie ja mit einer bestehenden roten verbunden
> werden soll. Aber sie darf auch nicht grün sein, weil sie
> mit einer anderen grünen verbunden wird. Andererseits muss
> sie rot sein, weil sie mit einer grünen Ecke verbunden
> wird, und sie muss grün sein, weil sie mit einer roten
> Ecke verbunden wird.
>
> > Fazit: es ist nicht möglich, genau eine Ecke in einen
> bipartiten Kreis einzufügen.
>
> Die Sache ist. Das was du da oben beschrieben hast. Habe
> ich so eigentlich verstanden. Aber das ist doch auch nur
> ein Beispiel, oder??? Damit wäre der Beweis ja nicht für
> jedes ungerade n gezeigt, oder?
Richtig, auf diesem Weg genau genommen nicht. Denn es könnte ja sein, dass ich z.B. mit 17 Ecken trotzdem einen bipartiten Kreis bilden kann, indem ich nicht den Schritt 16+1 versuche, sondern z.B. 12+5. Aber auch das wäre noch leicht auszumerzen.
Es genügt doch aber die Erkenntnis von oben.
Sie gilt für jeden Kreis, also auch für jeden Hamiltonkreis. Er kann nur dann bipartit sein, wenn die Eckenzahl gerade ist.
Was sagt Dir das über die Voraussetzungen, die die Aufgabe trifft?
Jetzt bist Du doch fast fertig.
Trotzdem, wie ich gerade schon schrieb: eine wirklich lange Pause sollte das Vorankommen beschleunigen können.
Ciao,
rev
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:49 Mo 10.05.2010 | | Autor: | jaruleking |
Danke dir für alles.
Werde morgen nochmal versuchen dann alles etwas formal und schön aufzuschreiben.
Vielleicht haste ja lust und zeit drüberzuschauen.
Grüße
|
|
|
|
