Graphentherorie |
| 13.01.2005, 12:11 | Moeki | Auf diesen Beitrag antworten » | ||
Graphentherorie
Def: Ein Baum ist ein zusammenhängender Graph, der keine Kreise (mit mehr als einer Ecke) enthält. Bäume kann man unter anderem durch die folgenden Aussagen äquivalent charakterisieren:
Ich habe also die Definition eines Baumes und die entsprechenden Sätze (nämlich 1 und 4. Muss ich da überhaupt noch beweisen? Hat er mehr oder genauso viele Kanten, ist er nicht mehr kreisfrei und somit kein Baum. Hat er weniger Kanten, ist er nicht mehr zusammenhängend und somit kein Baum. Gruß, Moeki. |
||||
| 13.01.2005, 12:17 | Moeki | Auf diesen Beitrag antworten » | ||
diesbezüglich hätte ich noch ne zweite Aufgabe
Hier greifen die Sätze 1 und 2. Wären es 2 Wege, wäre es ein Kreis und somit kein Baum. Wäre es gar kein Weg, wären es einfach nur 2 nicht zusammenhängende Ecken und somit ebenfalls kein Baum. Ich kann mir nicht vorstellen, dass das als Beweis reicht |
||||
| 13.01.2005, 12:38 | JochenX | Auf diesen Beitrag antworten » | ||
ich denke zum ersten problem hast du recht. aber gabs bei zusammenhängend nicht noch unterscheidungen zwischen stark, schwach, einseitig zusammenhängend? wäre denn folgender graph nicht auch zusammenhängend: drei knoten, im kreis verbunden das wäre aber sonst nicht zur aussage 4) passend, denn hier ist ja nichts von dr knotenzahl gegeben..... oder ist das nur wage formuliert? genauso 5.... ich denke bei 4) und 5) muss jeweils der zusatz "bei n ecken" hinzu.... denn n ist gar nicht definiert hierbei.... mgf jochen edit: oder besser: bei einem n-eckigen graphen sind folgende ausagen äquivalent 1)... und dann bei 1 die anzahl der ecken streichen weil so wies das steht isses echt nicht gut |
||||
| 13.01.2005, 12:43 | kurellajunior | Auf diesen Beitrag antworten » | ||
| RE: Graphentherorie Hallo Moeki Das Problem mit den Beweisen ist, dass Du Voraussetzungen brauchst, auf die Dein Beweis fußt. Das sind andere bereits bewiesene Ausagen, Definitionen oder Axiome. Andere Grundlagen gibts es meiner Meinung nach nicht. Da bei 1. Die Definition bereits die Antwort enthält ist die Aufgabe nicht beweisbar, sondern nur mit einem Verweis auf die Definition zu beenden. Interessant wäre es 4. aus 1-3 zu beweisen! Für 2. brauchst Du eine Definition für einen Weg. Um die Aussage zu beweisen müsste die Wegdefinition etwa so lauten: Ein Weg hat genau zwei voneinander verschieden Endpunkte. Jede Kante ist ein Weg mit ihren Knoten als Endpunkte. Ein Weg kann aus zwei Teilwegen bestehen, wenn der Endpunkt des einen Wegs ein Endpunkt des anderen Wegs ist. Zwei Wege sind gleich, wenn sie sich in dieselben Teilwege zerlegen lassen. Jetzt kannst Du daran gehen zu beweisen, was passiert, wenn es keinen Weg gibt (1.Fall) und wie ein Graph aussehen muss, wenn es min. zwei Wege gibt. (2.Fall) Damit erklärst Du die notwendigkeit von "genau". Danach musst Du nur noch zeigen, dass ein Weg allen Bedingungen (1-3) eines Baumes genügt. Fertig. |
||||
|
|