0 Daumen
2,1k Aufrufe

Aufgabe:

Sei G = (V,E) ein Graph. Eine Kante e ∈ E heißt Brücke, wenn der Graph G0 = (V,E \{e}) mehr Zusammenhangskomponenten als G hat. Beweisen oder widerlegen Sie: Ein Graph, in dem alle Knoten geraden Grad haben, enthält keine Brücke.

Problem/Ansatz:

Kann mir jemand bei dieser Aufgabe eventuell Helfen?

Avatar von

Vom Duplikat:

Titel: Beweisen oder widerlegen: Ein Graph in dem alle Knoten geraden Grad haben, enthält keine Brücken.

Stichworte: brücke,knoten,komponenten,graph,graphentheorie

Sei G=(V,E) ein Graph. Die Kante e Element E heisst Brücke, ....

Ein Graph in dem alle Knoten geraden Grad haben, enthält keine Brücken.

Kann mir jemand helfen ? Ich komme nicht mal auf ein Ansatz!

Hilfe !

1 Antwort

+3 Daumen

Die Summe der Grade aller Knoten ist gerade, weil jede Kante zu genau zwei Knoten gehört.

Also gibt es keinen Graphen, der genau einen Knoten mit ungeradem Grad hat.

Entfernt man aus einem Graphen, in dem alle Knoten geraden Grad haben, eine Kante, dann kann keine neue Zusammenhangskomponente entstanden sein, weil in ihr genau ein Knoten ungeraden Grad hätte.

Avatar von 105 k 🚀

vielen Dank :)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community