Beweis Graph hat Zyklus über Induktion

Neue Frage »

9halbe Auf diesen Beitrag antworten »
Beweis Graph hat Zyklus über Induktion
Meine Frage:
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?
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. unglücklich

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. unglücklich


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.
9halbe Auf diesen Beitrag antworten »

Hey, erstmal vielen Dank für deine Antwort!

Also ich versuche das jetzt mal zu verstehen und zu verarbeiten Lehrer

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

Zitat:
Original von 9halbe
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?

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). Augenzwinkern
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?
 
 
9halbe Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
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). Augenzwinkern


In meinem Fall haben aber alle Knoten 2 Nachbarn. Dann ist es doch egal welchen ich entferne oder?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von 9halbe
In meinem Fall haben aber alle Knoten 2 Nachbarn. Dann ist es doch egal welchen ich entferne oder?

Ja. Ich rede ja auch vom allgemeinen Fall - es nützt schließlich nichts, den Beweis nur über das Viereck zu führen.
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?
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.
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?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von 9halbe
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.

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.
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?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von 9halbe
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?

Wir waren in Fall 1 - erinnerst du dich?
9halbe Auf diesen Beitrag antworten »

Stimmt...sorry Gott
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?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von 9halbe
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.

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 .
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?
HAL 9000 Auf diesen Beitrag antworten »

Es fehlt:

Zitat:
Die minimale Nachbarzahl unter allen Knoten sein , und es sei einer der Knoten mit dieser Nachbaranzahl.

Wurde in Fall 1 nicht benötigt - in Fall 2 allerdings schon (werden wir noch sehen).


Zitat:
Der übrig gebliebene Graph hat nun die Knotenanzahl n und die Kantenanzahl n-1.

Damit ist wohl die Frage beantwortet, ob du meinen letzten Beitrag überhaupt irgendwie zur Kenntnis genommen hast: Anscheinend nicht. unglücklich

Wozu gebe ich Fehlerhinweise, wenn du dann doch dieselben alten falschen Zeilen copy+paste-mäßig wieder aufwärmst? Finger2
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?
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

Zitat:
Original von 9halbe
Sei G = (V,E) ein ungerichteter Graph mit n > 2 Knoten. Beweisen
Sie, dass G einen Zyklus hat, falls |E| > n ? 1 ist.

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.
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?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von 9halbe
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.

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. unglücklich



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?
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.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von 9halbe
Vom rienen Gefühl her würde ich dann jetzt v wieder löschen, genau wie alle m Kanten, die an v hängen.

Hallo? Bist du noch da? Das haben wir doch vorher sowieso schon getan,

Zitat:
Original von HAL 9000
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.

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.
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.
HAL 9000 Auf diesen Beitrag antworten »

Also gut: Was ist denn deine Idee, wie wir hier zu einem Zyklus kommen?
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.
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:

Zitat:
Original von HAL 9000
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...

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. unglücklich

--------------------------

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.
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?
HAL 9000 Auf diesen Beitrag antworten »

Ich hab inzwischen kapituliert (siehe EDIT).
9halbe Auf diesen Beitrag antworten »

Okay, schade.
Trotzdem danke für deine Hilfe! Wink Freude
HAL 9000 Auf diesen Beitrag antworten »

Der Induktionsschritt nochmals in geraffter Form, gültig für alle :

Zitat:
Wir betrachten einen Graphen mit sowie , für den wollen wir nachweisen, dass dort stets ein Zyklus existiert. Wir bezeichnen mit die Menge der mit Knoten verbundenen Kanten aus , es sei nun . Sei nun irgendein Knoten mit .

Wir entfernen erstmal Knoten und alle damit verbundenen Kanten, d.h., wir betrachten Knotenmenge sowie Kantenmenge , und stellen dabei insbesondere fest.


Fall 1:

Hier ist , also ist auf die Induktionsvoraussetzung anwendbar, es gibt einen Zyklus in . Wegen ist das auch ein Zyklus in .

Fall 2:

Unter den mit verbundenen Kanten suchen wir uns zwei aus, nennen wir die damit verbundenen Knoten und und die zugehörigen Kanten sv sowie tv.

Fall 2.1: Kante st liegt in

Damit haben wir einen Dreierzyklus stv in , und sind fertig.

Fall 2.2: Kante st liegt nicht in

Wir betrachten den Graphen mit . Nun gilt und damit

,

es kann also auch auf die Induktionsvoraussetzung angewandt werden, es existiert also ein Zyklus in .

Fall 2.2.1: Der Zyklus enthält nur Kanten aus .

Wie in Fall 1 sind wir dann wegen fertig.

Fall 2.2.2: Der Zyklus enthält nicht nur Kanten aus , d.h., auch Kante st.

Wir entfernen Kante st aus dem Zyklus und schließen die so entstehende Lücke durch die vormals entfernten, aber beide in liegenden Kanten sv sowie tv. Das entstehende Gebilde ist ein vollständig in liegender Zyklus, also sind wir auch hier fertig.


Ist m.E. kein großes Ding, wenn man nur konzentriert bei der Sache bleibt.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »