Beweise in der Graphentheorie

Neue Frage »

RVD Auf diesen Beitrag antworten »
Beweise in der Graphentheorie
Schönen Tag, ich bin auch mal wieder da, mit einer meiner "Lieblingsaufgaben".

Zeigen Sie: Wenn in einem Graphen für jede Kante die Summe der Grade beider Endknoten ungerade ist, dann gibt es in dem Graphen keinen Kreis mit einer ungeraden Länge.

Jemand eine Idee wie man das beweist?
Huggy Auf diesen Beitrag antworten »
RE: Beweise in der Graphentheorie
Da bietet sich ein Widerspruchsbeweis an. Von den Endknoten einer Kante muss einer einen geraden Grad und der andere einen ungeraden Grad haben. Jetzt wandere um einen Kreis herum. Es folgen dann abwechselnd Knoten von geradem und ungeradem Grad.
Was folgt für die Grade der Endknoten der letzten Kante bei der Wanderung, wenn der Kreis eine ungerade Zahl von Kanten hat?
RVD Auf diesen Beitrag antworten »

wenn ich einen kreis bilden soll, ist doch der anfangsknoten auch der endknoten, wie sollen die denn dann überhaupt einen unterschiedlichen grad haben?

und wenn beide knoten den gleichen grad haben, is die summe ihrer gerade doch immer gerade. also kann die summe der gerade von anfangs und endknoten in einem kreis doch nie ungerade sein oder?!

also deswegen weiß ich auch nicht wie ich deine anweisung als beispiel aufzeichnen sollte
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von RVD
wenn ich einen kreis bilden soll, ist doch der anfangsknoten auch der endknoten, wie sollen die denn dann überhaupt einen unterschiedlichen grad haben?

In der Aufgabe ist doch vom Anfangs- und Endknoten einer Kante die Rede, nicht vom Anfangs- und Endknoten des Kreises. Jetzt klar?
RVD Auf diesen Beitrag antworten »

ah ok, ich habs verstanden.

bei deinem beispiel folgt doch daraus, dass die beiden endknoten der letzten kante geraden und ungeraden grad haben oder? also ist die summe der beiden dann auch ungerade, ich seh bei solchen "beweise"-aufgaben aber nie den zusammenhang. ich muss jetz schon wieder immer nachlesen, was denn überhuapt gezeigt werden soll und wo da der zusammenhang ist

edit: wo ist denn da auch eigentlich der beweis durch gegensatz?! wenn die beiden endknoten jeder kante, jeweils geraden und ungeraden grad haben, ist ihre summe doch ungerade, also das was gezeigt werden sollte
Huggy Auf diesen Beitrag antworten »

Na, so ganz verstanden hast du es doch nicht.

Es folgt, dass die Endknoten der letzten Kante des Kreises den gleichen Grad haben, wenn der Kreis aus einer ungeraden Zahl von Kanten besteht. Dann ist die Summe dieser beiden Knotengrade aber gerade. Nun soll aber die Summe bei jeder Kante ungerade sein,

Widerspruch!

Du solltest einfach die Aufgaben sorgfältig lesen und erst dann versuchen, sie zu lösen, wenn du dir sicher bist, alles verstanden zu haben. Das Aufmalen einiger Beispiele ist dabei oft hilfreich.
 
 
RVD Auf diesen Beitrag antworten »

ich meinte, dass ich verstanden habe, was du meintest, also das ich dich aufgabe falsch gelesen habe. ist auch heute hier unerträglich heiß hier und ich bekomme es nicht so richtig nachvollzogen. trotzdem vielen dank, werde mir das ganze nachher, wenns hoffentlich etwas kühler ist nochmal ansehen.

danke auf jeden fall
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »