 |
 |
 |
 |
 |
 |
Startseite » Forum » Durchschnittsgrad ~ Minimalgrad
Durchschnittsgrad ~ Minimalgrad
Universität / Fachhochschule
Graphentheorie
Tags: Durchschnittstheorie, Graphentheorie, Minimalgrad, Subgraph
 
|
  |
|---|
|
Ich habe folgende Aufgabe: "Der Durchschnittsgrad eines Graphen, ist definiert durch (2e(G))/|V(G)|." Beweisen Sie, dass jeder Graph einen Subgraphen G′ enthält, so dass δ(G′)≥d(G)/2. In der Tutorübung wurde gesgat, wir sollen so rangheen, dass wir den Graphen kompeltt nehmen und dann Knoten mit "zu kleinem Grad" löschen und schauen sollen, wie sich das auswirkt. Wenn ich einen Knoten lösche, dessen Grad kleiner als der Durchschnittsgrad von ist, so kann der Mindestgrad größer werden, muss aber nicht, da durch das Löschen des Knotens auch alle mit ihm verbundenen Kanten gelöscht werden und somit auch der Grad der benachbarten knoten sinkt. Wie beweise ich das also? Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.) |
|
 |
|
Soll das auch ein sein, oder wie ist definiert? Ah, offenbar ist der Minimalgrad! Man kann den Satz per Induktion nach Anzahl der Knoten beweisen. Bei Graphentheorie macht man das gerne, indem man ein "minimales Gegenbeispiel" betrachtet und einen Widerspruch erzeugt. Sei also ein Graph mit Knoten und Kanten und es gebe keinen Teilgrphen mit . Insbesondere ist . Sei ein Knoten vom Grad . Der Graph der durch Löschen von entsteht, hat einen Knoten und Kanten weniger als G. Was kannst du deshalb über aussagen? |
 |
|
Minimalgrad |
|
|
|
Dann müsste größer sein, als vor dem Löschen von oder? Aber wie komm ich dann auf einen Widerspruch? |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
940881
940864