Graphen und Bäume

Aufrufe: 63     Aktiv: 01.01.2022 um 20:07

0
Hallo zusammen und frohes Neues, meine Übungsgruppe und ich verzweifeln momentan an diesen beiden Aufgaben. Hat jemand einen Tipp oder Ansatz?

4. Zeigen Sie: Jeder Graph G mit δ(G) ≥ 2 enthält einen Kreis der Länge mindestens
    δ(G) + 1.
    Hinweis: Wählen Sie zunächst einen Weg maximaler Länge. Argumentieren Sie, warum          man aus einigen der Knoten dieses Weges einen Kreis der gesuchten Länge bilden kann.

5. Ein Baum ist ein zusammenhängender Graph, der keine Kreise enthält. Zeigen Sie, dass ein Graph G genau dann ein Baum ist, wenn zwischen je zwei verschiedenen Knoten von G genau ein Weg existiert

Vielen Dank
Diese Frage melden
gefragt

Punkte: 15

 

1
Ihr müsst einfach nur mit euren Definitionen arbeiten (und den Hinweis nutzen).   ─   zest 01.01.2022 um 20:02

Beispiele ausprobieren hilft auch oft.   ─   mikn 01.01.2022 um 20:07
Kommentar schreiben
0 Antworten