Graphentheorie |
12.05.2010, 20:51 | gzm | Auf diesen Beitrag antworten » |
Graphentheorie ich habe eine weitere aufgabe die ich leider nicht lösen kann.. Ich soll zeigen, dass ein Baum T=(V,E) mit |V|>1 , 2+ (Summenzeichen)v€V3 ( deg(v) -2 ) Blätter hat. V3= { v € V | deg(v)>(gleich) 3 }. wäre echt sehr lieb wenn mir jmd helfen und paar tipps geben würde... |
||
12.05.2010, 22:05 | kiste | Auf diesen Beitrag antworten » |
Warum kommst du mit dem Standardansatz Induktion nicht durch? |
||
12.05.2010, 22:07 | gzm | Auf diesen Beitrag antworten » |
danke für den tipp...werde ich versuchen... |
||
13.05.2010, 13:59 | gzm | Auf diesen Beitrag antworten » |
also ich habe es versucht aber muss nochmal nachfragen wegen dem induktionsanfang... ich muss v=3 einsetzen..aber komm beim summenzeichen durcheinander..was muss ich als startwert nehmen und was steht über dem summenzeichen?? |
||
13.05.2010, 14:20 | kiste | Auf diesen Beitrag antworten » |
Wieviele Knoten mit Grad größer gleich 3 hast du den in einem Baum mit 2 Knoten?! |
||
13.05.2010, 14:24 | gzm | Auf diesen Beitrag antworten » |
gar keins.. ? |
||
Anzeige | ||
|
||
13.05.2010, 14:25 | kiste | Auf diesen Beitrag antworten » |
Genau, also wird über nichts summiert. Damit ist die Summe einfach 0 |
||
13.05.2010, 14:33 | gzm | Auf diesen Beitrag antworten » |
ok..aber wie soll das dann beim indukt.schluss sein? also mein summenzeichen? IS: v-->v+1 aber wie summiere ich alles? ich glaube ich habe das immer noch nicht verstanden |
||
13.05.2010, 15:12 | kiste | Auf diesen Beitrag antworten » |
Nein, mach dir überhaupt einmal klar wie man deine Behauptung zeigen will. Der Beweis selbst ist nicht länger als 3 Zeilen... |
||
13.05.2010, 16:08 | gzm | Auf diesen Beitrag antworten » |
ich weiß es nicht kannst du mir bitte weitere tipps geben?? |
||
13.05.2010, 16:15 | kiste | Auf diesen Beitrag antworten » |
Du willst doch Induktion machen. Wie bekommst du von einem Baum mit n+1 Knoten einen Baum mit n Knoten, damit du die Induktionsvorraussetzung benutzen kannst? |
||
13.05.2010, 16:22 | gzm | Auf diesen Beitrag antworten » |
1+ der baum mit n knoten ??? |
||
13.05.2010, 16:38 | kiste | Auf diesen Beitrag antworten » |
Was soll 1 + der baum mit n Knoten bedeuten?! |
||
13.05.2010, 16:47 | gzm | Auf diesen Beitrag antworten » |
das ich 1knoten mehr hab als bei meinem ursprünglichem baum ... ?? |
||
13.05.2010, 17:54 | kiste | Auf diesen Beitrag antworten » |
Das beantwortet doch in keinster Weise meine Frage. Und die Antwort auf meine Frage ist wirklich nicht schwer |
||
13.05.2010, 19:29 | gzm | Auf diesen Beitrag antworten » |
ich kanns mir denken dass es bestimmt einfach ist aber daruf zu kommen ist halt manchmal schwer... könntest du mir vllt einen ansatz für den induktionsschluss geben??? |
||
13.05.2010, 20:44 | kiste | Auf diesen Beitrag antworten » |
Um von einem Graphen einen kleineren Graphen zu erhalten muss man doch Knoten entfernen. Damit der Graph ein Baum bleibt darf man aber nicht irgendeinen beliebigen Knoten entfernen. Welche Art von Knoten darf man nur entfernen damit es noch ein Baum bleibt? |
||
13.05.2010, 20:46 | gzm | Auf diesen Beitrag antworten » |
man darf nur ein blatt entfernen... |
||
13.05.2010, 20:47 | kiste | Auf diesen Beitrag antworten » |
Dann mach das doch und führe dann eine tolle Fallunterscheidung durch je nachdem welcher Grad der Nachbar deines Blattes ist. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|