Graphentheorie < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:54 Di 31.05.2005 | | Autor: | squeezer |
Hallo
sei $G = (V, E)$ ein Graph mit mindestens fünf Ecken. Zeigen Sie, dass $G$ oder der zu $G$ Komplementärgraph [mm] $G^C$ [/mm] einen Kreis enthält.
Vielen Dank für Ihre Hilfe, ich weiss überhaupt nicht wie ich das ganze formal aufschreiben kann. Wie kann man überhaupt (formell und ohne Skizze) herausfinden, dass $G$ einen Kreis enthält.
Squeezer
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:57 Di 31.05.2005 | | Autor: | Zyllyn |
naja wie schon im anderen Posting geschrieben ist das mit dem formal nicht so mein Ding :)
schau dir einfach noch mal die Definition aus der Vorlesung an (z.B. für einen Kreis). Mit denen als Grundlage sollte sich ein ordentlicher Beweis führen lassen.
Meine Idee für dieses Problem:
so ne Art Hochzählen
Also du konstruierst zwei Graphen gleichzeitig (das Original und sein Komplement).
Wir beginnen mit dem Originalgraph. Wenn eine Kante hier nicht mehr reinpasst ohne einen Kreis zu erzeugen, dann kommt sie in den Komplementgraphen.
Eine Ecke -> keine Kante
Zwei Ecken (eine neue Kante) -> eine Kante
Drei Ecken (zwei neue Kanten) -> eine (weitere) im Originalgraphen, eine im Komplement (macht 2/1)
Vier Ecken (drei neue Kanten, langsam wirds eng) -> eine weitere Kante im Originalgraphen, zwei im Komplement (macht 3/3)
Fünf Ecken (vier neue Kanten, schon vorbei *g*) -> in jeden Graphen passt nur noch eine Kante ohne einen Kreis zu erzeugen
so anschaulich haben wirs gezeigt (von einem Beweis bin ich aber bestimmt noch sehr weit weg)
ich glaub es gab nen Satz über die maximale Anzahl von Kanten in einem Baum (kreisfreier Graph). Wenn ihr den Satz schon hattet, dann ist es einfach darauf aufzubauen.
Ein Baum hat n-1 Kanten.
Ein vollständiger Graph hat [mm] \bruch{n*(n-1)}{2} [/mm] Kanten.
Die Summe aus Anzahl Kanten im Graph + Anzahl Kanten im Komplementgraphen = Anzahl im Vollständigen Graphen.
damit Graph und Komplement keine Kreise enthalten muß gelten:
[mm] 2*(n-1)\ge\bruch{n*(n-1)}{2}[/mm]
und das Ausrechnen führt zu
[mm] 4\ge n[/mm]
der Umkehrschluss ist dann, für n>4 gilt es nicht mehr, sprich ab fünf Ecken enthalten entweder der Graph oder sein Komplement (oder beide) einen oder mehrere Kreise
|
|
|
|
