Induktion auf Graphen |
| 28.10.2009, 18:54 | plizzz | Auf diesen Beitrag antworten » | ||
| Induktion auf Graphen wir haben folgende Aufgabe auf unserem Übungszettel gestellt bekommen:
Nun habe ich die Aufgabe folgendermaßen per Induktion gelöst: [attach]11693[/attach] Wie man sieht, gab es allerdings nur 1/4 darauf. Meine Tutorin meinte, ich könne so eine Induktion bei Graphen nicht anwenden, da es nicht sicher sei, dass ich jeden Baum so erzeugen könnte. Nun habe ich aber doch gezeigt, dass es egal ist, wie ich den Knoten anfüge, und die Formel immer Gültigkeit hat. Da ich den Knoten beliebig anfügen kann, kann ich so doch induktiv jeden Baum erzeugen und dann müsste der Beweis doch richtig sein. Zu sagen ist hierbei noch, dass wir isomorphe Graphen als gleich betrachten und es nur um endliche Graphen geht. Mir geht es dabei gar nicht darum, die Punkte für die Aufgabe zu bekommen, sondern einfach darum, dass ich nicht verstehe, was daran falsch sein soll. Also: Ist der Beweis richtig und wenn nicht, kann mir jemand genau erklären, warum das nicht so gehen soll? Vielen Dank schonmal, plizzz Edit: Bilder bitte als Anhang im Board hochladen und auf externe Hoster verzichten. Verkleinert habe ich es auch noch ein wenig 
Gruß, Reksilat. |
||||
| 29.10.2009, 00:54 | Reksilat | Auf diesen Beitrag antworten » | ||
Hi plizzz,
Sie meinte wohl, dass sie nicht sicher sei, denn andernfalls hätte sie Dir einen Baum zeigen können müssen, den man so nicht konstruieren kann. Ich finde Deinen Beweis plausibel und auch naheliegend. Induktion ist bei Bäumen eine sehr geläufige Beweismethode. Der Form halber hätte man vielleicht von einem beliebigen Baum mit n+1 Knoten ausgehen sollen, von dem man ein Blatt entfernt und dann auf den Restbaum Induktion anwenden kann - der Beweis bleibt dabei aber gleich. Gruß, Reksilat. Edit: Interessant wäre auch noch, worauf Du den einen Punkt bekommen hast.
|
||||
| 29.10.2009, 15:07 | plizzz | Auf diesen Beitrag antworten » | ||
Ok danke, dann habe ich mich ja nicht völlig zum Affen gemacht, als ich auf meinem Standpunkt verharrt habe. Könntest du das mit deiner Induktionsmethode nochmal genauer ausführen? Hat unser Prof so in der Art auch schon häufiger angewandt, aber so wirklich verstanden habe ich das Prinzip noch nicht. |
||||
| 29.10.2009, 18:19 | Reksilat | Auf diesen Beitrag antworten » | ||
Damit man gar nicht erst in die Verlegenheit kommt, ob man jeden Baum wirklich so basteln kann (kann man aber trotzdem!), sollte man vielleicht eher folgendermaßen vorgehen: IV: -Alle Bäume mit n Knoten erfüllen die Behauptung. IS: - Sei eine Baum mit n+1 Knoten gegeben. - Wähle ein Blatt x (ein solches existiert!) - dieses hängt an einem Knoten y - entferne Blatt x - Du erhältst einen Baum mit n Knoten, der die Behauptung erfüllt und in dem y entweder ein Blatt oder ein innerer Knoten ist - Nun gehst Du so vor wie oben. (Fallunterscheidung für y) Ist im Prinzip genau das gleiche, nur dass der Baum hier immer kleiner wirst. Da muss man sich nicht überlegen, ob man jeden Baum durch Anhängen von neuen Blättern konstruieren kann. Gruß, Reksilat. |
||||
| 29.10.2009, 18:40 | plizzz | Auf diesen Beitrag antworten » | ||
Ok, nur noch mal zum Verständnis: Ich mache den IA mit n=2 (klar) und habe daraus die IV. Dann nehme ich mir einen beliebigen Baum mit n+1 Knoten. Jetzt muss ich praktisch beweisen, dass ich immer von n+1 auf n kommen kann, sodass die IV erfüllt ist (in diesem Fall: ich entferne ein Blatt und erhalte dadurch dann einen Baum mit n Knoten). Danach gehe ich wieder von n->n+1 und zwar hänge ich jetzt den entfernten Knoten x wieder da an, wo ich ihn entfernt habe und zeige, dass dabei alles gut geht (Fallunterscheidung y). Also spare ich mir praktisch zu zeigen, dass ich so jeden Baum konstruieren kann und zeige stattdessen, dass ich immer von n+1->n kommen kann, sodass die IV erfüllt ist. Wäre super, wenn du nochmal dein ok geben könntest, falls das so richtig ist oder mich eben berichtigen könntest, falls etwas nicht stimmt. Ich denke nämlich, dass ich jetzt endlich die ganzen Induktionsbeweise richtig schnallen kann, die unser Prof da gebracht hat. MfG plizzz |
||||
| 30.10.2009, 01:18 | Reksilat | Auf diesen Beitrag antworten » | ||
Diesen Satz verstehe ich nicht ganz. Die Induktionsvoraussetzung (IV) ist doch, dass die Behauptung für jeden Teilbaum mit n Knoten gilt. Ist vielleicht auch nur ein Formulierungsproblem - wichtig ist, dass es für Dich nachvollziehbar ist. Du kannst ja auch mal ein wenig nach Induktionsbeweisen in der Graphentheorie googeln. Das verschafft ebenfalls Sicherheit. Gruß, Reksilat. |
||||
| Anzeige | ||||
|
|
||||
| 30.10.2009, 09:50 | plizzz | Auf diesen Beitrag antworten » | ||
Ich meine halt, dass ich zB in diesem Fall immer ein Blatt entfernen kann, dann erhalte ich einen Baum mit n Knoten. Wenn ich jetzt nicht immer einen Blatt finden würde (was natürlich Schwachsinn ist), könnte ich nicht auf einen Baum mit n Knoten kommen. |
||||
| 30.10.2009, 14:19 | plizzz | Auf diesen Beitrag antworten » | ||
Um mein Problem nochmal anhand einer Aufgabe zu erklären:
Angenommen, ich möchte jetzt die Hinrichtung (Eulersch => [...]) durch Induktion über V(G)=n zeigen und mache den I.A. mit n=3. Jetzt nehme ich mir einen beliebigen Eulerschen Graphen mit n+1 Knoten. Aber jetzt kann ich ja nicht einfach einen Knoten entfernen und behaupten, ich habe jetzt einen Eulerschen Graphen mit n Knoten, da das ja nicht unbedingt stimmt. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
