wann ist graph ein baum?

Question

ich verstehe im Moment nicht, wann ein Graph ein Baum ist. Zum Beispiel hat er 15 Ecken und 30 Kanten, ist es dann ein Baum?

Wie kann ich das herausfinden? Es muss ja die Euler Formel gelten und zwar die Anzahl der Knoten = Anzahl der Kanten + 1, das ist hier jedoch nicht der Fall, weil es ja 15 Ecken (Knoten) sind? Und es müssten 31 Ecken sein. Außerdem muss er Kreisfrei und zusammenhängend sein. Ist das korrekt?

für eine Antwort :).

Answer 1

> wann ein Graph ein Baum ist

Wenn er zusammenhängend ist und keine Kreise hat.

> Zum Beispiel hat er 15 Ecken und 30 Kanten, ist es dann ein Baum?

Nein.

> das ist hier jedoch nicht der Fall

Also ist es kein Baum.

> Außerdem muss er Kreisfrei und zusammenhängend sein.

Das ist die definiernde Eigenschaft eines Baumes. Nicht jeder Graph mit n Ecken und n-1 Kanten ist ein Baum.