0 Daumen
357 Aufrufe

Aufgabe:

Gegeben sei ein Graph G = (V, E) mit |V | ≥ 2 Knoten. Zeigen Sie die Äquivalenz folgender Aussagen:
i) Zwischen zwei beliebigen Knoten vi, Vj ∈ V existiert genau ein Pfad.
ii) G ist ein Baum.

Problem/Ansatz:

Ich weiß leider nicht, wie die Aufgabe gelöst wird... für Hilfe wäre ich dankbar

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Mach dir erstmal klar, was ein Baum ist: Ein zusammenhängender ungerichteter Graph ist ein Baum, wenn er keine Kreise enthält.

Zu i) => ii). Das kannst du mit einem Widerspruch machen. Nimm an, dass dein Graph mindestens ein Kreis enthält und führe das mit i) zu einem Widerspruch.

Zu ii) => i). Das kannst du auch per Widerspruch zeigen. Angenommen, es gäbe für mindestens zwei Knoten mehr als einen Pfad. Was kannst du daraus schließen?

Avatar von 15 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community