3-zusammenhängender Graph < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:03 Do 09.02.2006 | | Autor: | Tyr7 |
| Aufgabe | Satz: Jeder 3-zusammenhängende Graph G=(V,E) enthält eine Kante e, so dass G [mm] \circ [/mm] e wieder 3-zusammenhängend ist.
Der Beweis:
Angenommen, die Aussage ist falsch. Dann ist für jede Kante e=(u, v) der Graph G [mm] \circ [/mm] e höchstens 2-zusammenhängend und besitzt eine trennende Menge S mit |S| [mm] \le [/mm] 2. Da G 3-zusammenhängend ist, muss der durch die Kontraktion von e entstandene Knoten x in S liegen. Somit existiert ein Knoten w [mm] \not\in [/mm] {u, v}, so dass {x, w} den Graphen G [mm] \circ [/mm] e trennt. Damit ist T = {u, v, w} eine trennende Menge in G. da keine echte Teilmenge von T trennend sein kann, hat jeder Knoten aus T einen Nachbarn in jeder Zusammenhangskomponente C von G - T.
Wir wählen nun die Kante e, den Knoten w und die Zusammenhangskomponente C so, dass |C| minimal ist. Sei y ein Nachbar von w in C.
Wiederum existiert zur Kante f=(w, y) ein Knoten z, so dass G -{w, y, z} unzusammenhängend ist. Wie vorher hat jeder Knoten aus {w, y, z} einen Nachbar in den Zusammenhangskomponenten von G - {w,y, z}.
Da e = (u, v) [mm] \in [/mm] E, existiert eine Zusammenhangskomponente D von G-{w, y, z}, die weder u noch v enthält. Betrachte die Nachbarn von y in D. Da y in C liegt, muss jeder Nachbar von y in D selbst liegen. Da sowohl D als auch C zusammenhängend sind, folgt daraus D [mm] \subseteq [/mm] C. Mit y [mm] \in [/mm] C \ D ergibt sich ein Widerspruch zur Minimalität von |C|. |
Hallo,
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
zur Erklärung: G [mm] \circ [/mm] e heisst die Kante e entfernen, indem die zwei Knoten von e zusammengefasst werden. Soll kontrahieren heißen.
so das ist der lange Beweis.
Im Grunde ist mir die Vorgehensweise klar, nur mit dem Schlussatz komme ich nicht klar.
Am Anfang wähle ich C mit y und sage, dass C minimal ist (sonst hätte ich es nicht gewählt). Am Ende ist es aber ein Widerspruch, weil y [mm] \in [/mm] C ist?
Aber y war in C doch auch am Anfang und da war es noch ok? Und am Ende nicht?
Oder geht es eher darum, dass D in C enthalten ist und somit C nicht minimal ist, weil darin noch eine andere Zusammenhangskomponente sich versteckt? Aber dann dürfte C immer nur aus einem Knoten bestehen...
Das Ganze wird gebraucht um den Satz von Kuratowski (das mit K5 und K3,3 :)) zu beweisen.
Vielen Dank
Tyr
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
|
|
| |
|
Hallo Tyr,
mit Deiner letzten Bemerkung hast Du recht: der Widerspruch wird hergeleitet zur
Annahme, C sei minimal mit der Eigenschaft. Komponente einer solchen Konfiguration zu sein, denn es wird nachgewiesen, dass dann ein solches [mm] D\subseteq [/mm] C mit [mm] D\neq [/mm] C
existieren muesste.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 01:27 Fr 10.02.2006 | | Autor: | Tyr7 |
Hallo Mathias,
also liegt der Widerspruch darin, dass ich am Anfang etwas angenommen habe, was am Ende nicht wahr ist. Also ist meine Überlegung: am Anfang wars OK, später nicht, falsch?
Es war von Anfang an falsch, und am Ende habe ich es gezeigt.
Aber wie sieht es damit aus, wenn ich einen Graphen konstruiere, wo C nur aus dem Knoten y besteht. Dann gibt es gar kein D und C wird immer minimal sein.
Der Beweis kann dann aber in so ner Form nicht mehr durchgeführt werden.
Irgendwie verstehe ich es nicht, wie ein allgemeingültiges Lemma mit einem "für diesen Fall" konstruierten Graphen bewiesen werden soll?
Vielen Dank und viele Grüße
Tyr
|
|
|
| |
|
Hallo und guten Morgen,
also nochmal das Prinzip:
Im Beweis nimmt man an, fuer jede Kante e sei [mm] G\slash [/mm] e (das ist die Standard-Notation fuer Kontraktion) nicht 3-zush.
Dann nimmt man e und w und C so wie beschrieben, dass |C| minimal ist,
betrachtet eine Kante von w zu einem Knoten y in C (muss es geben) und
wendet auf diese Kante [mm] f=\{w,y\} [/mm] nochmal die Schlussweise an, um ein D zu erhalten, Dieses D muss ganz in C liegen, darf y nicht enthalten und fuehrt zum Widerspruch.
Ich hab mir das gerade mal schematisch aufgemalt, so kann man dem Beweis
ganz gut folgen. Hab leider momentan keinen Scanner verfuegbar bzw weiss nicht, wie man die hier bedient.
Also aus der Annahme (die ja durch den Beweis als falsch nachgewiesen wird)
folgt insbesondere, dass C nicht nur y enthalten koennte.
Ich wuerde mich beim Verstaendnis des Beweises nicht darauf einlassen, verstehen zu wollen, warum die behaupteten Konfigurationen fuer alle Faelle klappen (also auch fuer
[mm] C=\{y\}), [/mm] denn wenn es fuer [mm] C=\{y\} [/mm] nicht klappt, zeigt dies zunaechst gar nichts, solange nicht klar ist, dass dieser Fall tatsaechlich auftreten kann.
Konzentrieren wuerd ich mich auf das Verstaendnis, warum jeden einzelne Folgerung,
die in der Gedankenkette gemacht wird, zwingend ist.
Und wie gesagt/geschrieben: Malen !
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 15:11 Fr 17.02.2006 | | Autor: | Tyr7 |
Hallo,
es hat ein wenig gedauert, da ich mich bis jetzt mit Färbungen uw. beschäftigen musste. Aber jetzt wieder bei dem Thema lässt mir das keine Ruhe.
Um das Lemma zu beweisen, möchte ich zeigen, dass es keinen Graphen gibt, wo nach der Kontraktion einer (beliebigen) Kante der Graph 2-zusammenhängend ist. Wenn es so wäre, würde mein Lemma nicht gelten.
Also konstruiere ich 3-zusammenhängende Graphen, kontrahiere beliebige Kanten und prüfe ob der Graph vielleicht 2-zusammenhängend ist. ( Natürlich nicht so ganz willkürlich)
Dabei kommt einmal raus, dass C nicht nur aus y bestehen kann, denn dann klappt es nur mit der Kante e (u,v) aber nicht mit den anderen (es gibt ja in diesem Fall drei Kanten (u,y), (v,y) (w,y))
Also nehme ich noch einen Knoten z der Nachbar von y ist. Verbinde den noch zu mind. 2 aus den {u, v, w} Knoten, damit der Graph 3-zusammenhängend ist. Der Widerspruch klappt immer noch nicht, da es immer eine Kante gibt, wo es nicht klappt, also der Graph nach der Kontraktion immer noch 3-zusammenhängend ist.
Jetzt nehme ich noich einen Knoten a, den ich mit w,y,z verbinde. Dann klappt es, aber nur wenn a nur mit diesen drei Knoten verbunden ist. Wenn ich a zB mit u verbinde dann geht es nicht mehr.
Irgendwie sehr verwirrend, bei den vielen Möglichkeiten. Das Malen hilft mir hier auch nicht, da ich nicht so ganz verstehe, worauf ich hier hinaus möchte.
Die Fragen im einzelnen:
1. Wieso muss {w, y, z} eine trennende Menge sein? Ich könnte doch genauso {w,y,u} nehmen...
Oder handelt es sich bei {w, y, z} um solchen Graphen, wo es nicht geht und es reicht aus, da im Lemma steht "Jeder 3-zusammenhängende Graph" und dieser mit {w, y, z} gehört zu "jedem" Graphen?
2. Was hat die Minimalität von C für eine Bedeutung? Im Moment sehe ich es so, dass es gesagt wurde, damit ich später einen Widerspruch habe. Aber ich könnte es ja nicht sagen, so hätte ich auch keinen Widerspruch :)
Vielen Dank und viele Grüße
Tyr
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Mo 20.03.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
