Beweis Graph hat Zyklus über Induktion |
22.05.2017, 17:59 | 9halbe | Auf diesen Beitrag antworten » | ||||
Beweis Graph hat Zyklus über Induktion Sei G = (V,E) ein ungerichteter Graph mit n > 2 Knoten. Beweisen Sie, dass G einen Zyklus hat, falls |E| > n ? 1 ist. (Hinweis: Induktion über n). Meine Ideen: Also ich habe mir das so gedacht: Für einen Graph G, der nur n Knoten hat, für den gilt die IV. IA: n=3 und somit E>n-1=2. Also hat G einen Zyklus. Nun füge ich einen Knoten n hinzu, damit muss der neue Gesamtgraph V'=n+1 Knoten haben. Für die neue Kantenanzahl gilt dann nach der Formel |E|> n-1, dass der neue Graph mindestens (n+1)-1 Kanten haben muss, also mehr als n , also n+1 mindestens. Die IV kann ich doch nicht hier anwenden, da diese doch erst ab 2 Knoten gilt. für n>2 Und dann habe ich mir das jetzt so überlegt: Ich habe den alten Graphen G1 mit n Knoten und dieser hat nach Formel mehr als n-1 Kanten (mindestens) --> also mind. n und der neue Graph mit Knotenzufügung G2 hat mehr als n Knoten, also n+1. => G2 - G1 < Anzahl der Kanten des einen zugefügten Knotens E1. n+1 - n < E1. E1 > 1, also mind. 2 Kanten. kann man das so nachvollziehen? Der neue Knoten hat nun mind. 2 Kanten, und nach IV hab ich einen Zyklus. Nur die IV gilt erst ab einer Anzahl von 2 Knoten. Oder kann ich das trotzdem benutzen? |
||||||
22.05.2017, 20:31 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
So wie du die den Induktionsschritt beschreibst, funktioniert das nicht: Du musst für jeden Graphen mit und nachweisen, dass die Behauptung gilt. Also nicht nur für solche Graphen, die aus einem Graphen mit und durch bloßes Anfügen von Knoten und Kanten entstehen. Beispiel: Betrachten wir ein normales Viereck, also vier Knoten reihum verbunden durch insgesamt vier Kanten. Ein solcher Graph entsteht nicht aus einem Graphen mit 3 Knoten und mindestens 3 Kanten durch bloßes Anfügen eines Knotens und (einer oder mehrerer) Kanten. Es ist also nicht so, dass man irgendwas "anfügt", sondern eher so, dass man von einen bestimmten Knoten (mit gewissen angenehmen Eigenschaften) entfernt, d.h., es ist dann . Außerdem entfernt man alle mit verbundenen Kanten, deren Menge mit bezeichnet sei. Der verbleibende Graph sollte möglichst die Induktionsvoraussetzung erfüllen - wenn nicht, dann muss man evtl. nachhelfen, durch (temporäres) Hinzufügen neuer Kanten etwa... Wie auch immer, der nach Induktionsvoraussetzung dann existierende Zyklus ist dann auch Zyklus im Graph , sofern er keine der neu hinzugefügten Kanten enthält. Falls doch, muss man noch etwas basteln... So funktioniert es tatsächlich - ich hab natürlich entscheidende Stellen noch offengelassen, etwa nach welchem Kriterium man den Knoten auswählt ... du sollst ja auch was zu tun haben. |
||||||
22.05.2017, 20:43 | 9halbe | Auf diesen Beitrag antworten » | ||||
Hey, erstmal vielen Dank für deine Antwort! Also ich versuche das jetzt mal zu verstehen und zu verarbeiten Ich gehe jetzt mal davon aus, dass mein IA korrekt ist. IS: Sei nun ein Graph mit . Achso, wenn ich mir das jetzt bildlich vorstelle. Mein IA ist ja das "Dreieck". Wenn ich da aber etwas wegnehme, habe ich ja weniger als 3 Knoten und die brauche ich doch mind. oder? Muss ich dann im IA mit anfangen? |
||||||
22.05.2017, 20:48 | 9halbe | Auf diesen Beitrag antworten » | ||||
Wenn ich bei n=4 anfange, also das verbundene Quadrat mit 4 Kanten, dann habe ich im IA einen Zyklus. Und wenn ich davon jetzt eine Ecke wegnehme, z.b. unten rechts, und die beiden Kanten die zu der Ecke führten, dann bleiben noch 3 Ecken und 2 Kanten. Kein Zyklus. Und jetzt muss ich wieder eine Kante einfügen? Kann ich nicht z.b. die beiden unteren Punkte "verschmelzen"? Dann fällt nur ein Punkt und eine Kante weg. Bringt mich das weiter? |
||||||
22.05.2017, 20:51 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Der Induktionsschritt muss nur für funktionieren. Ich versteh also nicht diese seltsamen Diskussionen, die du da immer wieder führst.
So sieht's wohl aus. Gut, ich verrate mal noch was: Man entfernt am besten zu Beginn den (bzw. einen der) Knoten mit der minimalen Nachbarzahl . Und für diese minimale Nachbarzahl unterscheidet man die Fälle (einfach) und (etwas komplizierter). |
||||||
22.05.2017, 20:56 | 9halbe | Auf diesen Beitrag antworten » | ||||
Okay gut. Also nochmal. Ich entferne den Knoten v und 2 Kanten mit denen v verbunden ist. Dann füge ich eine Kante hinzu. und jetzt muss ich bestimmt durch etwas ersetzen oder? |
||||||
Anzeige | ||||||
|
||||||
22.05.2017, 20:58 | 9halbe | Auf diesen Beitrag antworten » | ||||
In meinem Fall haben aber alle Knoten 2 Nachbarn. Dann ist es doch egal welchen ich entferne oder? |
||||||
22.05.2017, 20:59 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Ja. Ich rede ja auch vom allgemeinen Fall - es nützt schließlich nichts, den Beweis nur über das Viereck zu führen. |
||||||
22.05.2017, 21:06 | 9halbe | Auf diesen Beitrag antworten » | ||||
Okay, also muss ich noch 2 Fälle unterscheiden. 1. Fall: v ist ein Blatt, also m=1 und 2. Fall: v ist kein Blatt, also m>1. Richtig? |
||||||
22.05.2017, 21:33 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Ja, wobei ich auch noch m=0 (es gibt isolierte Knoten) in den Fall 1 gleich mit reingepackt habe - ist ja schließlich auch möglich. |
||||||
22.05.2017, 21:37 | 9halbe | Auf diesen Beitrag antworten » | ||||
Okay, also. Fall 1: Falls v ein Blatt ist oder ein isolierter Knoten, entferne diesen und die Kante {u,v} (also die Kante, die zu dem Punkt führt) und noch einen weiteren Knoten. Und wenn man jetzt einen weiteren entfernt hat, was passiert dann? |
||||||
22.05.2017, 22:56 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Warum das? Nein, nur Knoten v und die evtl. Kante dahin, mehr wird nicht entfernt. Nun zähle mal durch, dann wirst du feststellen, dass der Restgraph genug Kanten enthält, um die Induktionsvoraussetzung darauf anwenden zu können. |
||||||
22.05.2017, 22:58 | 9halbe | Auf diesen Beitrag antworten » | ||||
Okay also V' hatte ja n+1 Knoten und wenn man einen entfernt sind es wieder n Knoten, wie bei der ursprünglichen Knotenmenge V. Aber was ist, wenn z.b. der Punkt mit 5 anderen Knoten verbunden war. Dann müssen doch alle 5 Kanten auch entfernt werden oder? |
||||||
22.05.2017, 23:02 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Wir waren in Fall 1 - erinnerst du dich? |
||||||
22.05.2017, 23:03 | 9halbe | Auf diesen Beitrag antworten » | ||||
Stimmt...sorry |
||||||
23.05.2017, 09:09 | 9halbe | Auf diesen Beitrag antworten » | ||||
Also nochmal. Fall 1: Falls v ein Blatt ist oder ein isolierter Knoten, entferne diesen und die Kante {u,v} (also die Kante, die zu dem Punkt führt). Dieser verbleibende Graph hat jetzt also noch n Knoten und n-1 Kanten. Genau so sah der Graph in der IV auch aus. Also erfüllt dieser Graph die Behauptung. So? |
||||||
23.05.2017, 10:11 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Nein: Wir gehen im Induktionschritt von einem Graphen mit sowie aus. Für den um einen Knoten sowie die damit verbundenen Kanten (m=0 oder m=1) reduzierten Graphen gilt dann sowie . |
||||||
23.05.2017, 14:36 | 9halbe | Auf diesen Beitrag antworten » | ||||
Also, was wir bis jetzt hatten: IV: G ist ein beliebiger ungerichteter Graph mit i Knoten. G hat einen Zyklus, falls die Anzahl der Kanten |E| > n-1 sind. IS: Sei G' ein ungerichteter Graph mit einer Anzahl an |V'|=n+1 Knoten und |E'| > n Kanten. 1. Fall: Grad von v <=1. Das heißt ja, dass v in keinem Zyklus drin sein kann, denn dann müsste der Grad mind. 2 sein. Lösche v (adjazent zu w) und zugehörige Kante e={v,w}. Der übrig gebliebene Graph hat nun die Knotenanzahl n und die Kantenanzahl n-1. Daraus folgt dann mit der Induktionsannahme, dass G' einen Zyklus hat. Nach Konstruktion von G' ist jeder Zyklus von G' auch ein Zyklus von G. Daher: G hat auch einen Zyklus. Stimmt der Fall so? |
||||||
23.05.2017, 14:55 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Es fehlt:
Wurde in Fall 1 nicht benötigt - in Fall 2 allerdings schon (werden wir noch sehen).
Damit ist wohl die Frage beantwortet, ob du meinen letzten Beitrag überhaupt irgendwie zur Kenntnis genommen hast: Anscheinend nicht. Wozu gebe ich Fehlerhinweise, wenn du dann doch dieselben alten falschen Zeilen copy+paste-mäßig wieder aufwärmst? |
||||||
23.05.2017, 15:05 | 9halbe | Auf diesen Beitrag antworten » | ||||
Okay, den ersten Teil habe ich jetzt zugefügt. Und das 2.te habe ich auch noch nicht ganz verstanden gehabt, aber jetzt habe ich es glaube ich. Dann hat also die Kantenanzahl jetzt den Wert mindestens n. Also immer noch mehr als in der IV. Und damit muss der Zyklus ja noch bestehen. Denn jeder Zyklus in G' ist auch in G. Richtig? |
||||||
23.05.2017, 15:18 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Ja, schwere Geburt. Ich bedauere es, dass ich nicht schon ganz oben im Eröffnungsposting dein Copy+Paste-Gehabe kritisiert habe
und das einfach stillschweigend als |E| > n-1 gelesen habe, was ja gleichbedeutend mit ist. Mein Versäumnis, solche Schlampigkeiten darf man von Anfang an nicht durchgehen lassen. |
||||||
23.05.2017, 15:27 | 9halbe | Auf diesen Beitrag antworten » | ||||
Okay.. Dann jetzt zum 2. Fall. Sei v aus G' ein Knoten mit d(v)>1. Mein Gedanekngang: Jetzt muss v und die zwei Kanten gelöscht werden. Und die Lücke die dann entsteht, da füge ich wieder eine Kante ein. Wäre das so richtig? |
||||||
23.05.2017, 15:37 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Teilweise richtig - aber man kann nicht nur zwei der Kanten löschen, sondern muss alle mit verbundenen Kanten löschen, wenn man Knoten selbst löscht - ansonsten hängen ja irgendwelche Kanten "lose" in der Luft, das ist nicht zulässig bei einem Graphen. Zählen wir doch erstmal durch, ob nach Entfernung des Knotens sowie der damit verbundenen Kanten der Restgraph noch genügend Kanten hat, indem wir uns von der "anderen" Seite nähern: Jeder Knoten hat mindestens Nachbarn, das macht insgesamt mindestens Kanten im Ausgangsgraphen, nach Abzug der Kanten immerhin noch mindestens Kanten im Restgraphen mit Knoten, und wir wissen ja hier in diesem Fall . Allerdings ist das nicht genug, denn im worst-case ist , das ist eine Kante zuwenig, um die Induktionsvoraussetzung anwenden zu können. Was kann man da tun? Betrachten wir doch mal zwei der Nachbarknoten von , nennen wir sie und (dass es die gibt, ist wegen ja klar). Gibt es eine Kante zwischen und , sind wir sofort fertig - Dreieckzyklus ! Gibt es sie nicht, so ergänzen wir sie temporär in unserem reduzierten Graphen mit Knoten und dann mindestens Kanten... Wie geht's nun weiter? |
||||||
23.05.2017, 15:52 | 9halbe | Auf diesen Beitrag antworten » | ||||
Mmh, ich verstehe nicht so ganz, warum man die dann hinzufügen sollte. Vom rienen Gefühl her würde ich dann jetzt v wieder löschen, genau wie alle m Kanten, die an v hängen. |
||||||
23.05.2017, 15:55 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Hallo? Bist du noch da? Das haben wir doch vorher sowieso schon getan,
Nochmal: Im worst-case haben wir allein durch diese Löschoperation eine Kante zuwenig! An dem einfachen Beispiel mit dem Viereck demonstriert: Nehmen wir dort eine Ecke sowie die beiden anliegenden Kanten weg, bleiben 3 Ecken und 2 Kanten übrig, auf die die Induktionsvoraussetzung nicht angewandt werden kann, und wo wie man sieht auch kein Zyklus vorhanden ist. |
||||||
23.05.2017, 16:03 | 9halbe | Auf diesen Beitrag antworten » | ||||
Ich verstehe gerade nicht was du meinst. Also das mit der Kante zwischen s-t-v schon, das ist ja auch klar. Aber dann verstehe ich nicht worauf du hinaus willst, falls wir die Kante erst hinzufügen. |
||||||
23.05.2017, 16:12 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Also gut: Was ist denn deine Idee, wie wir hier zu einem Zyklus kommen? |
||||||
23.05.2017, 16:15 | 9halbe | Auf diesen Beitrag antworten » | ||||
Also ich soll ja zeigen, dass die Behauptung stimmt. Und das soll für jeden Graph gelten. Mein Problem ist es, dass ich einfach nicht verstehe, dass ich die Graphen ändern darf. Es muss doch auch für jene gelten, die eben diesen Knoten von eben haben oder die Kante. Ich weiß, du wirst jetzt schreiben, es gilt ja auch für diese Graphen. Aber mir leuchtet das einfach noch nicht ein. |
||||||
23.05.2017, 16:21 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Ich hab meine Strategie bereits gestern 20:31 im großen und ganzen skizziert. Vermutlich hast du auch die nicht gelesen, ich zitiere jetzt trotzdem mal daraus:
Den ersten Teil haben wir jetzt erledigt, über den zweiten Teil muss man eben noch etwas nachdenken, etwa indem man sich das Viereckbeispiel mal ansieht und wie man da die Sache löst. Aber gleich von vornherein die Idee abblocken empfinde ich schon etwas kleingeistig von dir. -------------------------- EDIT: Was soll's, Ich geb es auf, hier der Rest des Beweises: Wir entfernen also Knoten und die damit verbundenen Kanten, fügen aber Kante s-t neu hinzu. Auf diesen so konstruierten Graphen kann man die Induktionsvoraussetzung anwenden, es existiert also ein Zyklus in diesem Graphen. Enthält dieser Zyklus die Kante s-t nicht, so besteht er nur aus Kanten des Originalgraphen und ist somit auch dort ein Zyklus. Enthält er die Kante s-t doch, dann entfernen wir diese Kante wieder und ersetzen sie durch den Kantenzug s-v-t des Originalgraphen, und erhalten damit einen Zyklus, der nur aus Kanten des Originalgraphen besteht, und sind damit hier ebenfalls fertig. |
||||||
23.05.2017, 16:32 | 9halbe | Auf diesen Beitrag antworten » | ||||
Also ich habe mir das jetzt mal aufgemalt und versuche es an Hand des Vierecks nachzuvollziehen. Zuerst der Graph in dem alle 4 Knoten außenrum miteinander verbunden sind. |V|=n+1=4 und |E|>n-1=3, also muss der Graph mind. 4 Knoten haben. Passt soweit. Jetzt entferne ich einen Knoten und 2 Kanten, dafür füge ich eine neue Kante hinzu, damit der Zyklus bestehen bleibt. ALso: |V'|=|V|-1=n+1-1=n=3 und |E'|=|E|-2+1=|E|+1=n+1+1=n+2. Soweit richtig? |
||||||
23.05.2017, 16:37 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Ich hab inzwischen kapituliert (siehe EDIT). |
||||||
23.05.2017, 16:42 | 9halbe | Auf diesen Beitrag antworten » | ||||
Okay, schade. Trotzdem danke für deine Hilfe! |
||||||
23.05.2017, 17:12 | HAL 9000 | Auf diesen Beitrag antworten » | ||||
Der Induktionsschritt nochmals in geraffter Form, gültig für alle :
Ist m.E. kein großes Ding, wenn man nur konzentriert bei der Sache bleibt. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|