kompletter graph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 23:47 Do 05.04.2007 | | Autor: | sara_20 |
| Aufgabe | Gegeben ist ein kompletter Graph K mit n vertex und mit gewichten auf edges.
Zeige folgendes:
Die Summe der Gewichte in jedem Kreis des Graphen K ist gerade wenn und nur wenn die Summe der Gewichte in jedem Dreieck gerade ist. |
Intuitiv ist mir das schon klar. Benuze auch dass ich insgesamt in jedem Kreis (oder Dreieck) nur gerade Zahl von ungeraden Kanten haben kann. Da die Summer ja gerade ist. Aber irgendwie fehlt mir der Beweis. Habe es versucht mit mathematischer indukzion, aber irgendwie muss ich dann zu viele Faelle unterscheiden wo die Gewichte in der Kontur (oder eventuel im Dreieck) ungerade sein koennen. Benutze auch dass ich ein Kreis von n ecken mit n-2 Dreiecken triangulieren kann.
Kann mir jemand weiterhelfen???
Besonders der Beweiss dass wenn alle Kreise eine gerade Summe an gewichten haben [mm] \Rightarrow [/mm] die summe von gewichten in jedem Dreieck ist gerade, ist mir ziemlich verwirrend. D.h. da weiss ich ueberhaupt nicht wie ich es angehen soll.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:02 Fr 06.04.2007 | | Autor: | sara_20 |
Habe es doch geschafft zu beweisen. Wenn es jemanden interessiert kann ich ja den Beweis aufschreiben.
Danke trotzdem!
Viele Gruesse aus Sarajevo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:38 So 08.04.2007 | | Autor: | sara_20 |
Also in einem Weg ist es ja leicht. Wenn die Gewichte in jedem Kreis gerade sind, dann sind sie auch im Dreieck. 
Nun, sei die Summe der Gewichte in jedem Dreieck gerade und nicht im jeden Kreis. Dann gibt es einen kreis der laenge k und die summe seiner gewichte ist ungerade. Teile diesen Kreis in einen Dreieck und in k-1 Kreis.
Der Dreieck hat entweder 0 oder zwei ungerade Gewichte. Auf jeden Fall findet man so einen anderen Dreieck bei dem die Summe der Gewichte ungerade ist(!). Es ohne Zeichnung ganz genau zu erklaeren ist ein wenig schwer. Der k Kreis hat eine ungerade Zahl von ungeraden Gewichten.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:41 So 08.04.2007 | | Autor: | sara_20 |
Man stellt zuerst fest dass der k-1 auch die summe von gewichten ungerade hat. Usw.Am Ende stellt man fest dass ein Dreieck ungerade zahl von gewichten hat. Kontradiktion!
|
|
|
|
![[cap]](/images/smileys/cap.gif "[cap]"){kind=small}
