Cliquen und Co. < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:41 Mo 22.06.2009 | | Autor: | Audience |
| Aufgabe | | Zeigen Sie, dass es jeder Graph mit 10 Knoten eine Clique der Größe 3 oder eine unabhängige (stabile) Menge der Größe 4 enthält. |
Hallo,
ich grüble an obiger Aufgabe schon etwas länger.
Mein Ansatz war, irgendwie abzuschätzen
a) wie viele Kanten man höchstens zu einem Graphen hinzufügen kann, sodass es keine Clique der Größe 3 gibt.
b) wie viele Kanten man mindestens zu einem Graphen hinzufügen muss, sodass es er keine stabile Menge der Größe 4 enthalten kann.
Daraus wollte ich dann einen Widerspruch herleiten.
Ist das so eine sinnvolle Strategie? Wie könnte man sonst rangehen?
Gruß,
Thomas
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:03 Di 23.06.2009 | | Autor: | felixf |
Hallo Thomas!
> Zeigen Sie, dass es jeder Graph mit 10 Knoten eine Clique
> der Größe 3 oder eine unabhängige (stabile) Menge der Größe
> 4 enthält.
>
> ich grüble an obiger Aufgabe schon etwas länger.
> Mein Ansatz war, irgendwie abzuschätzen
> a) wie viele Kanten man höchstens zu einem Graphen
> hinzufügen kann, sodass es keine Clique der Größe 3 gibt.
> b) wie viele Kanten man mindestens zu einem Graphen
> hinzufügen muss, sodass es er keine stabile Menge der Größe
> 4 enthalten kann.
>
> Daraus wollte ich dann einen Widerspruch herleiten.
> Ist das so eine sinnvolle Strategie?
Moeglich.
> Wie könnte man sonst rangehen?
Versuch es doch mal konstruktiv: nimm an, es gibt keine unabhaengige Menge der Groesse 4; d.h. sobald du vier Knoten waehlst, gibt es zwischen mindestens zweien dieser eine Kante.
Nehmen wir mal an du waehlst vier Knoten [mm] $v_1, \dots, v_4$ [/mm] und nur zwischen [mm] $v_1$ [/mm] und [mm] $v_2$ [/mm] ist eine Kante. Wenn du jetzt [mm] $v_2, \dots, v_5$ [/mm] anschaust, so muss dort ebenfalls eine Kante vorhanden sein, und da [mm] $v_2, \dots, v_4$ [/mm] keine haben muss es also eine Kante von [mm] $v_5$ [/mm] zu einem Knoten in [mm] $\{ v_2, \dots, v_4 \}$ [/mm] geben. Genauso gibt es von jedem weiteren Knoten eine Kante zu einem Knoten aus [mm] $\{ v_2, v_3, v_4 \}$. [/mm] Und genauso gibt es von jedem weiteren Knoten eine Kante zu einem Knonten aus [mm] $\{ v_1, v_3, v_4 \}$. [/mm] Kannst du das zusammen mit der Information, das es 10 Knoten gibt, eventuell nutzen um eine Clique zu finden?
(Es gibt noch mehr zu beachtende Faelle.)
Alternativ kannst du auch annehmen, es gibt keine 3er-Clique, und versuchen damit eine 4-unabhaengige Menge zu konstruieren. Immer wenn du 3 Knoten nimmst, sind mind. zwei davon nicht durch eine Kante verbunden. Hast du also zwei Knoten [mm] $v_1, v_2$, [/mm] die durch eine Kante verbunden sind, und nimmst irgendeinen dritten Knoten [mm] $v_3$, [/mm] so gibt es zwischen [mm] $v_1$ [/mm] und [mm] $v_3$ [/mm] oder zwischen [mm] $v_2$ [/mm] und [mm] $v_3$ [/mm] keine Kante.
Oder du nimmst an, es gibt weder eine 3-Clique noch eine 4-unabhaengige Menge, und zeigst einen Widerspruch. (Was aber vermutlich nur in einem der beiden obigen Ansaetze in `umgedrehter' Form enden wird.)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:14 Mi 24.06.2009 | | Autor: | Audience |
Hallo,
ich habe außer dem obigen Fall noch folgende Fälle gefunden:
b) [mm] {v_{1}, v_{2}, v_{3}, v_{4}} [/mm] hat zwei Kanten
i) Zwischen je 2 Knoten: o---o o----o
ii)Zwischen je 3 Knoten o---o--o o
c) die Menge hat 3 Kanten: o---o----o o
d) die Menge hat 4 Kanten: o---o---o---o
Aber zurück zum obigen Fall. Ich konnte aus deinem Ansatz folgern, dass zwischen [mm] {v_{1}, v_{3}, v_{4}} [/mm] und [mm] v_{i} [/mm] mit 5 <= i <= 10 und analog zwischen [mm] {v_{2}, v_{3}, v_{4}} [/mm] und den übrigen Knoten 6 Kanten existieren müssen. Das bedeutet, dass es einen Knoten in [mm] {v_{1}, v_{2}, v_{3}, v_{4}} [/mm] gibt, der auf jeden Fall mit zwei Knoten aus der übrigen Menge verbunden ist. Jetzt komme ich nicht wirklich weiter. Hast du noch einen Tipp?
Gruß,
Thomas
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:45 Do 25.06.2009 | | Autor: | wauwau |
Du sollst also beweisen, dass R(3,4) < 10 ist.
In der Tat ist R(3,4) (Ramseyzahlen - hoffe habt ihr schon durchgenommen) = 9.
Schau mal unter Ramseyzahlen nach, da gibt es einige Beweise, Abschätzungen usw, die dir bei der Problemlösung helfen können.
|
|
|
| |
|
Hallo wauwau,
ja, Ramsey-Zahlen haben wir behandelt.
Wir hatten sie aber etwas anders definiert:
Für alle k, c, n [mm] \el \IN [/mm] gibt es eine kleinste Zahl R(k, c, n) [mm] \el \IN, [/mm] genannt Ramsey-Zahl mit der folgenden Eigenschaft:
Ist V eine Menge mit |V| [mm] \ge [/mm] R(k, c, n) und f: [mm] \vektor{V \\ k} [/mm] -> C eine Färbung mit C = {0, 1, .., c - 1}, so gibt es eine monochromatische Teilmenge Y [mm] \subseteq [/mm] V mit |Y| [mm] \ge [/mm] n.
Hier interessant ist nur k = 2 (Färbung von Graphen).
Dafür haben wir folgende Schrank bewiesen:
R(2, c, n) [mm] \le 2^{nclog_{2}c}
[/mm]
Farben brauchen wir 2, nämlich 0 für keine Kante und 1 für Kante, also c = 2.
R(2, 2, n) [mm] \le 4^{n}
[/mm]
Aber nun habe ich ein Problem. Setze ich nun n = 3 ein, d.h. ich will eine Clique der Größe 3 garantieren, dann benötige ich höchstens [mm] 4^3 [/mm] = 64 Knoten in meinem Graphen G. Nicht unbedingt nützlich.
Habe ich irgendetwas nicht beachtet?
Gruß,
Thomas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:21 Sa 27.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
