Bipartite Subgraphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:55 Sa 26.01.2008 | | Autor: | Schroet |
| Aufgabe | Zeigen Sie, dass jeder ungerichtet Graph [mm] G = (V,E)[/mm] einen bipartiten Subgraphen [mm] H = (V, E'),[/mm] [mm]E'\subseteq E [/mm], mit [mm] \left|E'\right|\ge\bruch{\left|E\right|}{2}[/mm] enthält.
Hinweis: Wie würde ein Algorithmus eine Knotenpatition fingen bzw. eine gegebene verändern? |
Guten Tag.
Ich habe versucht die obere Aufgabe zu lösen und habe auch einen Algo "ausgedacht", jedoch sind einige Fragen während der Lösung aufgetaucht, die ich mir nicht beantworten konnte, deshalb bin ich auch hier.
Also zu meinem Lösungsansatz:
Idee: wir versuchen mit Hilfe der Tiefensuche aus dem ungerichteten Graphen einen Baum zu konstruieren, welchen wir zu einem bipartiten Graph transformieren können
Wir benutzen folgenden Algorithmus zu:
1. Setze [mm] V_1 := \emptyset [/mm], [mm] V_2 := \emptyset [/mm], [mm] E' := \emptyset [/mm]
2. Wähle beliebigen [mm]v_1\in V[/mm] als Startknoten und setze [mm]V_1 := V_1 \cup {v_1} [/mm]
für i:=1, i<n, i++
3. falls i ungerade dann k:=2, sonst k:=1
4. Suche Verbindung von [mm]v_i[/mm] zu einem beliebigen Nachbarknoten [mm]v_{i+1}\not\in{V_1}[/mm] und [mm] v_{i+1}\not\in{V_2}[/mm].
5. Setze [mm] V_k := V_k \cup {post(v_i)} [/mm] und [mm] v_{i+1} := post(v_i) [/mm] (für die Durchnummerierung gedacht)
6. Setze [mm] E' := E' \cup {e_i} [/mm], wobei [mm]e_1(v_i,v_{i+1})[/mm]
7. Gehe nach 3 bis es keine Verbindung mehr exisitiert.
Ich bin mir sicher, dass im Algorithmus ein paar Fehler drin sind (Indizes oder ähnliches), darum werde ich versuchen, mit meinen eigenen Worten beschreiben, was ich mir da ausgedacht habe.
Also. Wir wählen uns einen beliebigen Knoten [mm] v_1 [/mm] und setzen diesen als Startknoten. Dann definieren wir drei leeren Mengen E', [mm] V_1 [/mm] und [mm] V_2. [/mm]
Wir starten von dem Startknoten [mm] v_1 [/mm] an und packen diesen in die Menge [mm] V_1 [/mm] rein.
Dann suchen wir eine mögliche Verbingung zu einem Nachbarknoten [mm] (post(v_1)). [/mm]
Wir packen die Kante, die [mm] v_1 [/mm] und [mm] post(v_1) [/mm] verbindet in die Menge der Kanten E' und den Nachfolger [mm] (post(v_1)) [/mm] packen wir in die Menge [mm] V_2.
[/mm]
Wir nummerieren [mm] post(v_1) [/mm] als [mm] v_2.
[/mm]
Wir suchen möglichen Nachfolger von [mm] v_2 [/mm] der nicht in [mm] V_1 [/mm] und nicht in [mm] V_2 [/mm] liegt.
Wir packen den Nachfolger von [mm] v_2 [/mm] in die Menge [mm] V_1 [/mm] rein und die Kante in die Menge E'
usw.
Wir suchen also einen Weg von [mm] v_1 [/mm] zu anderen Knoten und packen somit abwechselnd die Knoten in die Mengen [mm] V_1 [/mm] und [mm] V_2.
[/mm]
Jetzt kommen die Fragen:
1. Wie treffe ich eine Fallunterscheidung, wenn G zusammenhängen oder nicht zshgd. ist?
2. Wie beweise ich, dass mein Algorithmus (fall er korrekt ist) korrekt arbeitet?
3. Weitere Problematik sehe ich in der Aufgabenstellung, wobei behauptet wird, das JEDER ungerichtete Graph einen bipartiten Subgraphen enthält.
4. Wie zeige ich diese Eigenschaft für ALLE Graphen? Induktiv? Mit welchem Ansatz?
5. Muss ich einen Verfahren (Algorithmus) entwickeln, der bestätigt, dass man Graphen beliebig zerlegen kann und somit einzelne kleine bipartitete Graphen bekommt?
6. Reicht es zu zeigen, dass man ungerichtete Graphen in Bäume transformieren kann, wodurch man einen bipartiten Graphen bekommt?
Ich bin noch ein Ersti, von daher fällt es mir nicht leicht, meine Gedanken sauber und präzise wiedergeben zu können, ich bitte um Verständnis und Feedback, was man besser schreiben/sagen könnte.
mfg
Schroet
Ich habe diese Frage in keinem anderen Forum gestellt!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:28 Sa 26.01.2008 | | Autor: | koepper |
Hallo,
> Zeigen Sie, dass jeder ungerichtet Graph [mm]G = (V,E)[/mm] einen
> bipartiten Subgraphen [mm]H = (V, E'),[/mm] [mm]E'\subseteq E [/mm], mit
> [mm]\left|E'\right|\ge\bruch{\left|E\right|}{2}[/mm] enthält.
>
> Hinweis: Wie würde ein Algorithmus eine Knotenpatition
> fingen bzw. eine gegebene verändern?
> Idee: wir versuchen mit Hilfe der Tiefensuche aus dem
> ungerichteten Graphen einen Baum zu konstruieren, welchen
> wir zu einem bipartiten Graph transformieren können
Die Idee funktioniert nicht, weil du gemäß Aufgabenstellung höchstens die Hälfte der Kanten entfernen darfst.
Stell dir vor, du hast einen vollständigen Graphen [mm] $V_n$ [/mm] mit n Knoten. Der hat [mm] $\frac{n * (n-1)}{2}$ [/mm] Kanten. Ein aufspannender Baum hat aber nur n-1 Kanten und daher müßtest du für n > 4 mehr als die Hälfte der Kanten entfernen, um aus dem Graphen einen Baum zu machen.
Warum ignorierst du denn den guten Hinweis in der Aufgabenstellung?
> 1. Wie treffe ich eine Fallunterscheidung, wenn G
> zusammenhängen oder nicht zshgd. ist?
gar nicht, das ist unerheblich. Bei nicht zusammenhängenden Graphen kann das Verfahren einfach auf alle Komponenten angewendet werden.
> 2. Wie beweise ich, dass mein Algorithmus (fall er korrekt
> ist) korrekt arbeitet?
das siehst du erst, wenn du ihn hast.
> 3. Weitere Problematik sehe ich in der Aufgabenstellung,
> wobei behauptet wird, das JEDER ungerichtete Graph einen
> bipartiten Subgraphen enthält.
Diese Aussage ist völlig trivial: Entferne alle Kanten und der Graph ist bipartit.
Das Problem liegt eben darin, daß du höchstens die Hälfte der Kanten entfernen darfst.
> 4. Wie zeige ich diese Eigenschaft für ALLE Graphen?
> Induktiv? Mit welchem Ansatz?
Der Algorithmus und seine Korrektheit liefern den Beweis.
Man kann zum Beispiel eine Induktion über die Anzahl der Knoten machen.
> 5. Muss ich einen Verfahren (Algorithmus) entwickeln, der
> bestätigt, dass man Graphen beliebig zerlegen kann und
> somit einzelne kleine bipartitete Graphen bekommt?
Ich verstehe nicht recht was du meinst:
Weißt du denn, was "bipartit" bedeutet?
> 6. Reicht es zu zeigen, dass man ungerichtete Graphen in
> Bäume transformieren kann, wodurch man einen bipartiten
> Graphen bekommt?
nein, siehe oben!
Gruß
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:44 So 27.01.2008 | | Autor: | Schroet |
Guten Tag!
Vielen Dank für die Antwort!
Ich habe mir gestern ein wenig Gedanken gemacht. Und zwar kann ich mein Algorithmus mit einem Schritt ergänzen, wobei mehr als die Hälfte der Kanten dann in dem bipartiten Subgraphen sind.
Also man spannt wie schon oben beschrieben einen Baum auf. Woraus zwei disjunkte Mengen [mm] V_1 [/mm] und [mm] V_2 [/mm] mit der Eigenschaft [mm]V := V_1 \cup V_2[/mm] entstehen. Danach schaut man sich diejenigen Kanten an, welche Knoten aus [mm] V_1 [/mm] mit den Knoten aus [mm] V_2 [/mm] verbinden. Wodurch [mm] E' \ge \bruch {|E|}{2} [/mm].
Soweit ich verstanden habe, dürfen die Knoten der Mengen [mm] V_1 [/mm] und [mm] V_2 [/mm] untereinander nicht verbunden sein (richtig?).
> Warum ignorierst du denn den guten Hinweis in der
> Aufgabenstellung?
Wie meinst du das? Ich versuche doch einen Algorithmus zu finden, der die Knoten so aufteilt, dass dadurch ein bipartiter Subgraph entsteht. Oder ist das die falsche Richtung?
mfg
Schroet
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:57 So 27.01.2008 | | Autor: | koepper |
Hallo,
> Ich habe mir gestern ein wenig Gedanken gemacht. Und zwar
> kann ich mein Algorithmus mit einem Schritt ergänzen, wobei
> mehr als die Hälfte der Kanten dann in dem bipartiten
> Subgraphen sind.
>
> Also man spannt wie schon oben beschrieben einen Baum auf.
> Woraus zwei disjunkte Mengen [mm]V_1[/mm] und [mm]V_2[/mm] mit der
> Eigenschaft [mm]V := V_1 \cup V_2[/mm] entstehen. Danach schaut man
> sich diejenigen Kanten an, welche Knoten aus [mm]V_1[/mm] mit den
> Knoten aus [mm]V_2[/mm] verbinden. Wodurch [mm]E' \ge \bruch {|E|}{2} [/mm].
ich sehe nicht, wie du das sichern willst.
> Soweit ich verstanden habe, dürfen die Knoten der Mengen
> [mm]V_1[/mm] und [mm]V_2[/mm] untereinander nicht verbunden sein (richtig?).
genau.
> > Warum ignorierst du denn den guten Hinweis in der
> > Aufgabenstellung?
>
> Wie meinst du das? Ich versuche doch einen Algorithmus zu
> finden, der die Knoten so aufteilt, dass dadurch ein
> bipartiter Subgraph entsteht. Oder ist das die falsche
> Richtung?
Ich denke, du hältst dich zu sehr an der Idee mit dem Baum fest.
Schau dir doch einfach mal den Algorithmus zur Ermittlung der Knotenpartition für bipartite Graphen an.
LG
Will
|
|
|
|
