Beweis Graphentheorie |
| 14.11.2014, 09:11 | webi | Auf diesen Beitrag antworten » | ||
| Beweis Graphentheorie 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 |
||||
| 14.11.2014, 09:51 | 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. |
||||
| 14.11.2014, 10:28 | 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 ? |
||||
| 14.11.2014, 14:16 | HAL 9000 | Auf diesen Beitrag antworten » | ||
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. |
||||
| 14.11.2014, 14:41 | Math1986 | Auf diesen Beitrag antworten » | ||
Man muss also maximal einen Knoten vom Grad Null entfernen. |
||||
| 14.11.2014, 14:44 | webi | Auf diesen Beitrag antworten » | ||
Irgendwie geht das Prinzip nicht ganz in meinen Kopf 
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 ? |
||||
| Anzeige | ||||
|
|
||||
| 14.11.2014, 15:02 | 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? |
||||
| 14.11.2014, 15:07 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Genau das sagt das Schubfachprinzip. 
|
||||
| 14.11.2014, 15:17 | webi | Auf diesen Beitrag antworten » | ||
Okay vielen Dank
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
