Graphentheorie Frage (2): zusammenhängende Graphen |
12.01.2013, 14:33 | Grapfik | Auf diesen Beitrag antworten » |
Graphentheorie Frage (2): zusammenhängende Graphen 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! |
||
12.01.2013, 15:04 | 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |