Graph der länge d < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:23 Mi 02.02.2005 | | Autor: | arzoo |
Kann mir jemand helfen bei diesem Beweis , ich weiß nähmlich nicht wie ich das machen soll .
Sei ein Graph G mit allen Knoten vom Grad >= d. Zeigen Sie, dass es immer einen Weg durch den Graphen gibt, dessen Länge zumindest d beträgt. (Ein Weg ist ein Kantenzug, in dem keine Kante mehrfach verwendet wird.)
|
|
| |
|
Hallo arzoo,
der Grad ist doch die Anzahl der Kanten, die in diesem Knoten enden, oder?
Dann kannst du doch Widerspruch zeigen: der längste Graph kann nicht weniger als d Kanten lang sein.
Wäre das der Fall, dann müsstest du ja nach n<d durchlaufenen Kanten in einer 'Sackgasse' stecken, d.h. du bist zu einem Knoten gegangen, von dem keine 'unverbrauchte' Kante mehr wegführt. Das kann aber nach weniger als d Schritten nicht der Fall sein, du hast ja dann höchstens (d-1) Kanten durchlaufen.
=> nach (d-1) Schritten ist überall noch mindestens eine Kante zum Weiterlaufen da und der Weg ist mindestens d Schritte lang
Hugo
|
|
|
|
