Beweis Graphentheorie

Neue Frage »

webi Auf diesen Beitrag antworten »
Beweis Graphentheorie
Hallo ich soll folgendes beweisen:

Beweisen Sie, dass jeder ungerichtete Graph G = (V , E)
(|V | >= 2) mindestens 2 Knoten mit gleichem Grad hat!

Allerdings weiß ich absolut nicht wo ich ansetzen soll, bitte um Hilfe
HAL 9000 Auf diesen Beitrag antworten »

Man könnte kurz sagen: Schubfachprinzip

Angewandt auf die Knotengrade in dem Graph, der um evtl. vorliegende leere Knoten bereinigt wurde.
 
 
webi Auf diesen Beitrag antworten »

Okay was meinst du mit bereinigen?
Eine Fallunterscheidung machen ?
Also Fall1:
Es gibt einen Knoten k0 mit dG(k0)=0
und
Fall2:
Es gibt keinen Knoten k0 mit dG(k0)=0
?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von webi
Okay was meinst du mit bereinigen?

Einfach diese Knoten von den weiteren Betrachtungen ausschließen: Wenn es gelingt, dass man unter den nichtleeren Knoten zwei mit gleichen Grad findet, dann ist man ja auch fertig.

Nach dieser Bereinigung bleiben nun mindestens zwei, oder aber kein Knoten übrig (genau ein Knoten geht nicht). Ist es keiner, d.h., alle Knoten haben Grad 0, ist man sowieso fertig, d.h. man kann sich auf den Fall von Knoten vom Mindestgrad 1 konzentrieren.
Math1986 Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Nach dieser Bereinigung bleiben nun mindestens zwei, oder aber kein Knoten übrig (genau ein Knoten geht nicht).
Ja, wobei man aber schon fertig wäre wenn es zwei Knoten mit Grad Null gäbe. smile Man muss also maximal einen Knoten vom Grad Null entfernen.
webi Auf diesen Beitrag antworten »

Irgendwie geht das Prinzip nicht ganz in meinen Kopf verwirrt
Okay wenn wir also Knoten vom Grad 0 ausschließen bleiben nur Knoten k mit 1 <= Grad(k) <= n-1. Irgendwie kann ich daraus aber nicht formal folgern dass daraus folgt das 2 Knoten den selben Grad haben ?
webi Auf diesen Beitrag antworten »

Vllt so: Wenn es jetzt n Knoten gibt und diese diese auf die max. n-1 Knotengrade verteilt werden müssen, muss es zwei geben die den gleichen Grad haben oder?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von webi
Vllt so: Wenn es jetzt n Knoten gibt und diese diese auf die max. n-1 Knotengrade verteilt werden müssen, muss es zwei geben die den gleichen Grad haben ?

Genau das sagt das Schubfachprinzip. Freude
webi Auf diesen Beitrag antworten »

Okay vielen Dank smile
Neue Frage »
Antworten »



Verwandte Themen

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