Beweis Graph hat Zyklus |
| 27.05.2013, 01:17 | Kat2 | Auf diesen Beitrag antworten » |
| Beweis Graph hat Zyklus Huhu, ist ja schon reichlich spät geworden, mal schauen ob noch wer da ist ^^ Also wir sollen folgendes beweisen: Sei g=(V,E) ein ungerichteter Graph mit n>2 Knoten. Beweisen Sie, dass G einen Zyklus hat, falls |E|>n-1 ist. Haben noch den Hinweis bekommen, das mit Induktion zu lösen. Meine Ideen: Aus der Vorlesung wissen wir, dass G genau dann ein Baum ist, wenn |E|=|V|-1, also sprich |E|=n-1 ist. Ich dachte mir, wenn einem Baum eine (oder mehrere) Kanten hinzugefügt wird, dann bekommt er doch einen Kreis, oder? Ich weiß ja, das ist es ja eigentlich, was ich beweisen soll, aber es ist doch eigentlich offensichtlich? oO muss ich die Induktion unbedingt machen? Induktionsanfang wäre ja dann bei n=3, und |E|>2. Der einzig mögliche Baum wäre ja dann praktisch ein "Dreieck", alle Knoten sind miteinander verbunden. Passt also, ist n Kreis. Induktionsvorraussetzung: Für n>2 und |E|>n-1 gilt: Der Graph G=(V,E) hat einen Kreis. Induktionsschritt: Betrachte G*=(V*,E*) mit |V*|=n+1. also muss ja jetzt |E*|>(n+1)-1=n sein. Was ja auch >n-1 ist. Aber wie ersetze ich jetzt |E*| durch |E|? Muss ich ja irgendwie geschickt konstruieren oder? Ich dachte mir, wenn wir die Knotenanzahl erhöhen, muss ja der Knoten auch mit dem Rest verbunden sein, also müssten wir ja noch eine Kante hinzufügen. Oder, weil wir ja im ursprünglichen Graphen nen Kreis haben, könnten wir ja auch die "unnötige", einen Kreis verursachende Kante nehmen um den neuen Knoten zu verbinden. Aber es steht ja nichts davon da, dass G bzw G* zusammenhängend sind, sondern nur ungerichtet O.O Andererseits, wenn man bedenkt, dass wenn |E|=n-1 ist, das n Baum ist, dann ist ja iwie doch klar, dass das zsmhängend ist... hmmm... Ich bin nicht ganz sicher, wie meine Gedanken überhaupt noch mit der Aufgabe zusammenhängen, aber das ist mir dazu eingefallen 
Wär schön wenn mir jemand helfen kann, und keine Sorge, das hat Zeit, ich hab Zeit, solange wir das lösen können, bin ich glücklich ^^ Zweiten Beitrag reinkopiert und gelöscht. Steffen oder ich sag einfach, ja gut, schmeißen wir halt noch nen knoten v dazu, machen den zu nem Blatt, indem wir noch ne Kante x dazuwerfen, und hey, |E*|=|E|+1, und |V*|=|V|+1=n+1, das wollten wir ja, Induktionsschritt und so, und weil ja in G schon ein Kreis war, fällt der ja nicht weg, wenn wir ein Blatt drankleben, und damit hat sich die Sache, G* hat auch einen Kreis, hurra. Ist es das, ist es so simpel, und muss ich das mathematischer schreiben? ^^ |
||
| 27.05.2013, 11:17 | RavenOnJ | Auf diesen Beitrag antworten » |
Wäre schön, wenn du deine Gedanken stringenter darlegen würdest. In der Kürze ..., du weißt. So wie das da steht, hat wohl niemand Lust sich damit zu beschäftigen. |
||
| 27.05.2013, 13:26 | Kat2 | Auf diesen Beitrag antworten » |
Jo, sorry, stimmt schon. Hat sich aber jetzt eh erledigt, habs selbst geschafft. Trotzdem danke =) |
||
| 27.05.2013, 13:30 | RavenOnJ | Auf diesen Beitrag antworten » |
Dann ist ja gut. Das Problem mit den Zusammenhangskomponenten hast du dann vermutlich auch im Griff gehabt. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
