zusammenhängender Graph

Neue Frage »

FelNa1109 Auf diesen Beitrag antworten »
zusammenhängender Graph
Hallo, ich hab Probleme mit folgender Aufgabe:

Sei ein Graph mit Knoten und Kanten. Zeigen Sie, dass zusammenhängend ist. Stimmt die Aussage auch für ? Wenn ja, bitte beweisen, wenn nicht bitte ein Gegenbeispiel angeben.

Sah für mich auf den ersten Blick ziemlich nach Induktion gerochen, also hab ichs probiert.

IA: 3 Knoten, Kanten mindestens 2 Kanten, also ist der Graph zusammenhängend

IV: Aussage für ein bewiesen.

IS: Und hier beginnt das Problem, weil ich ehrlich gesagt nicht weiter weiß, wie ich jetzt den Schritt machen muss. Hoffe mir kann jemand helfen. Dankeschön smile
FelNa1109 Auf diesen Beitrag antworten »

Ich hatte mir den Induktionsschritt in etwa so vorgestelllt:

Ich habe einen Graphen mit Knotenmenge und Kantenmenge

Wenn ich bei einem zusammenhängenden (!) Graphen einen weiteren Knoten hinzufüge, sprich , dann muss ich auch mindestens eine Kante hinzufügen um den Knoten mit dem Graphen zu verbinden, damit der neue Graph wieder zusammenhängend ist:
Also

zur zweiten Teilaufgabe, hätte ich einfach den IA genommen, da bei 3 Knoten und nur einer Kante der Graph nicht zusammenhängend ist (Gegenbeispiel)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »