0 Daumen
31 Aufrufe

Aufgabe:

Sei G ein einfacher, ungerichteter, nicht zusammenhängter Graph mit n Knoten und m=n-1 Kanten.

Beweisen Sie, dass mindestens eine Zusammenhangskomponente ein Baum ist.

von

1 Antwort

0 Daumen

Ein Kreis aus \(k\) Knoten hat \(k\) Kanten.

Ist jede Zusammenhangskomponente von \(G\) ein Kreis, dann benötigt man \(n\) Kanten.

Ist in einer Zusammenhangskomponente mit \(k\) Knoten ein Kreis mit \(p < k\) Kanten, dann benötigt man mindestens \(k-p\) Kanten um die nicht auf dem Kreis liegenden \(k-p\) Knoten mit der Zusammenhangskomponente zu verbinden. Die Zusammenhangskomponente hat also mindestens \(p + (k-p) = k\) Kanten.

von 3,3 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community