| 11.05.2004, 17:55 |
Maesta |
Auf diesen Beitrag antworten » |
Graphen, Bäume
Aufgabe:
Sei G=(V,E) ein zusammenhängender Graph mit n Knoten. Der Baumgraph “ (G) hat als Knoten die aufspannenden Bäume des Graphen G; zwei Knoten im Baumgraph “(G) sind durch eine Kante verbunden, wenn die beiden zugehörigen aufspannende Bäume T und d
Genau n-2 Kanten gemeinsam haben (da aufspannende Bäume genau n-1 Kanten haben, bedeutet dies automatisch, dass sich T und d in genau einer Kante unterscheiden). Zeigen Sie, dass der Baumgraph “(G) zusammenhängend ist.
Kann mir jemand helfen? Hab keine Ahnung :-( |
