matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieBipartiter Graph und Hamilto.
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Graphentheorie" - Bipartiter Graph und Hamilto.
Bipartiter Graph und Hamilto. < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Bipartiter Graph und Hamilto.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:44 Mo 10.05.2010
Autor: jaruleking

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

        
Bezug
Bipartiter Graph und Hamilto.: Antwort
Status: (Antwort) fertig Status 
Datum: 18:56 Mo 10.05.2010
Autor: reverend

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

Bezug
                
Bezug
Bipartiter Graph und Hamilto.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:08 Mo 10.05.2010
Autor: jaruleking

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....

Bezug
                        
Bezug
Bipartiter Graph und Hamilto.: Antwort
Status: (Antwort) fertig Status 
Datum: 19:14 Mo 10.05.2010
Autor: reverend

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

Bezug
                                
Bezug
Bipartiter Graph und Hamilto.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:23 Mo 10.05.2010
Autor: jaruleking

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?


Bezug
                                        
Bezug
Bipartiter Graph und Hamilto.: Antwort
Status: (Antwort) fertig Status 
Datum: 19:40 Mo 10.05.2010
Autor: reverend

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

Bezug
                                                
Bezug
Bipartiter Graph und Hamilto.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:47 Mo 10.05.2010
Autor: jaruleking

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....

Bezug
                                                        
Bezug
Bipartiter Graph und Hamilto.: Antwort
Status: (Antwort) fertig Status 
Datum: 19:53 Mo 10.05.2010
Autor: reverend

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

Bezug
                                                                
Bezug
Bipartiter Graph und Hamilto.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:05 Mo 10.05.2010
Autor: jaruleking


> 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?

Bezug
                                                                        
Bezug
Bipartiter Graph und Hamilto.: Antwort
Status: (Antwort) fertig Status 
Datum: 20:17 Mo 10.05.2010
Autor: reverend

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

Bezug
                                                                                
Bezug
Bipartiter Graph und Hamilto.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:36 Mo 10.05.2010
Autor: jaruleking


> 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....

Bezug
                                                                                        
Bezug
Bipartiter Graph und Hamilto.: Antwort
Status: (Antwort) fertig Status 
Datum: 20:48 Mo 10.05.2010
Autor: reverend

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




Bezug
                                                                                                
Bezug
Bipartiter Graph und Hamilto.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 21:00 Mo 10.05.2010
Autor: jaruleking


> 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?


Bezug
                                                                                                        
Bezug
Bipartiter Graph und Hamilto.: Antwort
Status: (Antwort) fertig Status 
Datum: 21:25 Mo 10.05.2010
Autor: reverend

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


Bezug
                                                                                                                
Bezug
Bipartiter Graph und Hamilto.: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]