| Autor |
Beitrag |
    
Katja
| | Veröffentlicht am Mittwoch, den 31. Januar, 2001 - 10:07: | 
|
Hallo könnte mir jemand bei der Lösung folgender Aufgabe helfen, da ich mit der Beweisführung nicht zurecht komme.
Beweisen sie: Ein endlicher Baum mit mindestens einer Kante besitzt mindestens zwei Knoten, deren Valenz genau 1 ist.
Es wäre echt klasse wenn mir jemand dabei helfen könnte.
Katja |
Katja
| | Veröffentlicht am Samstag, den 03. Februar, 2001 - 16:00: |
|
Also ich find das irgendwie unfair, allen helft ihr aber mir nicht und ich weiß nicht mehr weiter :-(((( |
Matroid (Matroid)
| | Veröffentlicht am Samstag, den 03. Februar, 2001 - 17:16: |
|
Hi Katja,
nehmen wir mal das Gegenteil an: in einem Baum habe höchstens eine Ecke die Valenz 1.
Dann gibt es eine Ecke mit Valenz >=2, denn der Baum soll ja mindestens eine Kante haben.
Ausgehend von dieser Ecke kann man dann aber einen Kreis finden, indem man einfach über irgendeine Kante zur nächsten Ecke geht, die auch Valenz >=2 hat usw. Da der Baum endlich ist, kommt man irgendwann zu einer Ecke, bei der man schon war, und hat einen Kreis gefunden.
Man muß sich dabei noch genau überlegen, daß man nicht in eine Sackgasse geraten kann, denn Sackgasse bedeutet ja, an einer Ecke mit Valenz 1 zu sein. Wenn es keine Ecke mit Valenz 1 gibt, kommt das ohnehin nicht vor. Wenn es aber genau eine Ecke mit Valenz 1 gibt, dann gibt es mindestens eine andere Ecke mit Valenz >=3, denn in Graphen ist die Anzahl der Ecken mit ungerader Valenz immer gerade.
Wenn man also in eine Sackgasse geraten ist, dann geht man nun in der Gegenrichtung. In dieser Richtung kann man nicht nochmals in eine Sackgasse geraten, denn es gibt ja nur eine Ecke mit Valenz 1. Man kann also jede Ecke, zu der man über eine Kante gelangt ist über eine andere Kante wieder verlassen. Da de Baum endlich ist kommt man also irgendwann zu einer Ecke ein zweites mal, hat also einen Kreis.
Gruß
Matroid |
|
