Graphentheorie Frage (2): zusammenhängende Graphen

Neue Frage »

Grapfik Auf diesen Beitrag antworten »
Graphentheorie Frage (2): zusammenhängende Graphen
Wink
Erneut Hallo,

Folgendes:

Es ist G ein Graph mit n Knoten und q Kanten.
Zeigen Sie, dass der Graph G ein zusammenhängender Graph ist für


Meine Idee(n):

Ein Graph G ist zusammenhngend, wenn je zwei Knoten in G verbunden sind. D.h. es gibt keine isolierten Knoten.
Das wiederum bedeutet für q, dass


Denn für q < n-1 folgt, dass es isolierte Punkte gibt (z.b. mit 3 Knoten und n-2 = 3-2 = 1 Kante..)

Also besitzt ist q mindestens gleich n-1.

Das wollte ich nun in obige Ungleichung einsetzen, das führt aber nicht zum erwünschten Erfolg.

Hat jemand einen Hinweis/Tipp für mich?

Vielen Dank!
IfindU Auf diesen Beitrag antworten »
RE: Graphentheorie Frage (2): zusammenhängende Graphen
Das Problem was du hast:

n-1 Kanten ist minimal, so dass der Graph zusammenhängend ist. Aber du kannst (außer für kl. n) die n-1 Kanten so legen, dass der Graph nicht zusammenhängend ist.

So kannst du dir 4 Knoten aufmalen, 3 davon mit einem Dreieck verbinden und der Graph ist mit 3 Kanten nicht zusammenhängend.

Was du aber zeigen sollst: Wenn du viele Kanten nimmst, kannst du die nicht so unglücklich legen, dass etwas unzusammenhängendes rauskommt.

Als Ansatz würde ich nehmen:
Angenommen wir haben so vielen Kanten, und der Graph ist nicht zusammenhängend, d.h. es gibt k Zusammenhangskomponenten. Und dann zeigst du dass du nicht alle Kanten unterbringst (ohne parallele Kanten oder Schleifen reinzubekommen).

Gibt sicher schönere, aber mir fällt gerade keiner ein.
Neue Frage »
Antworten »



Verwandte Themen

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