Beweis Baum min2Ecken min2Kant < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:01 Mi 19.12.2007 | | Autor: | Kar_o |
| Aufgabe | | Jeder Baum mit mindestens 2Knoten hat mindestens 2 Blätter. |
Also ich denke hier muss ich zunächst beweisen , dass mein Graph G kreifrei und zusammenhängen ist, weil erst dann weiß ich dass ich auch von einem Baum ausgehen kann. Oder?
Und Dann würde ich einfach an eines der beiden Blätter ein weiteres dranhängen und dann zeigen, dass es immer noch ein Baum ist. Stimmt die Richtung bei meinen Überlegungen?
Problem ist wie scheibe ich (insbesondere den 2.Teil) auf?
Hilfe ich hab das Gefühl ich werd irre!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:15 Mi 19.12.2007 | | Autor: | Zneques |
Hallo,
Also wenn das deine gesammte Aufgabe ist, dann hast du bereits einen Baum vorgegeben und sollst nun zeigen, dass für mindestens 2Knoten auch mindestens 2 Blätter vorhanden sind.
Kreisfrei und zusammenhängend sind natürlich die Eigenschaften die man dafür benötigt.
Angenommen es stimmt nicht. Wie würde denn ein Baum mit meheren Knoten und nur einen (/keinen) Blatt aussehen ?
(Wenn du einfach ein weiteres Blatt dranhängst, beweist du nur, dass ein Baum nach hinzufügen eines weiteren Blattes immernoch ein Baum ist. Auch nicht schlecht. ;) )
Ciao.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:24 Mi 19.12.2007 | | Autor: | Kar_o |
Wie würde denn ein Baum mit meheren Knoten und nur einen (/keinen) Blatt aussehen ?
Mehrere Knoten und nur ein/kein Blatt geht doch gar nicht ohne nicht irgendwo nen Kreis bilden zu müssen, weil man ja immer irgendwo am Ende einen Knoten hat der nicht mit einem dritten Knoten in verbinudng steht. Oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:22 Mi 19.12.2007 | | Autor: | Zneques |
Genau so ist es !
Das heißt es gibt keine Bäume mit 2 oder mehr Knoten die nur ein/kein Blatt haben.
Somit hat jeder Baum mit mindestens 2 Knoten mindestens 2 Blätter.
Das alles noch etwas netter formulieren und es ist dann dein Beweis.
Ciao.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:33 Mi 19.12.2007 | | Autor: | Kar_o |
Ja aber wie schreibe ich das nett, einfach in Sätzen oder wie?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:15 Do 20.12.2007 | | Autor: | Zneques |
Du musst dein "geht doch gar nicht" noch genauer begründen.
Zum Beispiel so :
Sei B ein Baum mit mindestens 2 Knoten.
1) Angenommen B hat kein Blatt. Dann bilden wir einen Pfad mit Start in einen beliebigen Knoten, indem wir immer einen Knoten hizufügen, der nicht der vorletzte Knoten war. Ein solcher muss existieren, da es keine Blätter gibt, und somit jeder Knoten min. 2 Nachbarn hat. Weil der Pfad endlos wird, gibt es irgendwann einen Knoten der sich wiederholt. Damit enthält der Pfad, also auch B einen Kreis.
Widerspruch !
2) Angenommen B hat genau ein Blatt. Dann bilden wir einen Pfad, der mit dem Blatt und dessen Nachbarn startet. Danach setzen diesen Pfad wie bei 1) fort und erhalten einen Kreis.
Widerspruch !
[mm] \Rightarrow [/mm] B hat mindestens 2 Blätter.
Ciao.
|
|
|
|
