Graphentheorie: Hamiltonkreise in teilabgeschlossenen Bäumen |
| 09.05.2013, 18:06 | blubbel | Auf diesen Beitrag antworten » |
| Graphentheorie: Hamiltonkreise in teilabgeschlossenen Bäumen ich komme hier nicht so richtig weiter.. Für einen Baum T sei T^n der Graph, der durch Hinzufügen aller Kanten zwischen je zwei Ecken u und v entsteht, für die der Abstand von u nach v in T kleiner gleich n ist. Es handelt sich also um eine Art partiellem transitiven Abschluss, wenn man so möchte 
Die Behauptung ist nun, dass für alle Bäume T der Graph T³ einen Hamiltonkreis enthält. Über Induktion der Eckenzahl geht bestimmt etwas, aber da hakt es in Moment etwas.. Über einen Tip wäre ich dankbar. Der offizielle Hinweistext ist im Bild unten. Ich wollte zunächst einen anderen Weg gehen, der jedoch scheitert.. mit dem Ansatz im Bild kann ich wenig anfangen. (Sei eine solche Ordnung gegeben, man füge ein Blatt hinzu. Wieso klappt das immer?) edit: Ich benötige die Antwort zu dieser Aufgabe nicht mehr, aber es könnte für jemanden ja interessant sein, also lasse ich sie drin (und weil ich den Thread eh nicht löschen kann
). |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
