 |
 |
 |
 |
 |
 |
Startseite » Forum » Zeige dass Graph ist zusammenhängend
Zeige dass Graph ist zusammenhängend
Universität / Fachhochschule
Graphentheorie
Tags: Diskrete Mathematik, Graphentheorie, zusammenhängend
 
|
  |
|---|
|
Sei ein einfacher Graph(ohne Schlingen oder mehrfachen Kanten) mit Knoten. Für je zwei Knoten die nicht durch eine Kante verbunden sind ist die Summe Ihre Grade(Anzahl Kanten die durch die Knote gehen) mindestens . Zeige dass diese Graph zusammenhängend ist. Mein Ansatz: Ich habe es versucht direkt zu lösen. Ich glaube das wäre der Fall wenn durch jede 2 Knoten einen Weg gibt und seit Wege(aber warum?) und Wanderung in diesem Fälle analog sind, dann entspricht es die Definition von zusammenhängend. Dann hab ich versucht es indirekt mit Widerspruch zu machen. Angenommen es wäre nicht zusammenhängend und Summe der Grade mindestens . Dann wie komme ich auf das Widerspruch? Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Hallo simssims, ich würde einen Widerspruchsbeweis machen. Nehmen wir an, dass der Graph in mindestens zwei Zusammenhangskomponenten zerfällt, also ist, wobei keine der Ecken von mit keiner der Ecken von verbunden ist. Nun gilt also mit und . Kannst du damit einen Widerspruch konstruieren? Gruß ermanus |
 |
|
Hallo ermanus, danke für deinen Antwort. Ich komme leider nicht viel weiter. Ich habe es graphisch gezeichnet und verstehe warum es gelten muss, aber kann es nicht mathematisch ausdrücken. soll ich jetzt die Summe der Grade betrachten und dann am Ende zum Widerspruch kommen dass es nicht zusammenhängend sein kann? Lg simssims |
|
|
|
Hallo simssims, wir überlegen mal: ein Knoten in hat höchstens den Knotengrad , entsprechend hat ein Knoten in höchstens den Grad . Nun betrachte die Summe der beiden Knotengrade ... |
|
|
|
Die Summe wäre dann ? Indem ich es versuche zu lösen und im Literatur ein ähnliches Beispiel angeschaut habe und mir ein konkretes Beispiel anschaue, habe ich mir eine andere Methode überlegt, die vielleicht es direkt beweisen kann. Also, nehmen wir an dass ich zwei Knoten und habe die nicht durch eine Kante verbunden sind, dann die Menge alle Knoten die zu durch eine Kante verbunden werden Oder zu durch eine Kante verbunden werden ist natürlich kleiner oder gleich n-2(weil so viel sind die verbliebende Knoten) und wenn ich daraus folgern kann(vieleicht mit mengentheoretische Überlegungen über Durchschnitt und Vereinigung) dass die Menge der Knoten die zu Und zu verbunden sind, größer gleich 1 ist, dann gäbe es zumindest eine Knote, die zu beide verbunden ist, und somit eine Wanderung zwischen diese beiden, was die Definition der zusammenhängende Graphen entspricht. Macht es Sinn? Danke für die Zeit, Lg simssims |
|
|
|
Ja. Das macht Sinn. Du hast also maximal Knoten, die mit einer Kante mit oder verbunden sind. Insgesamt hast du mindestens als Kantensumme. Nun benutze das Schubfachprinzip: du verteilst die Kanten auf die maximal Knoten als Endpunkte. Dann liegt ein Knoten als Endpunkt sowohl in der Kantenmenge, die von ausgeht als auch in der Kantenmenge, die von ausgeht. ist damit über diesen Knoten mit verbunden. |
 |
|
Vielen Dank! Sehr hilfreich! Lg simssims |
1537560
1537507