matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieCliquen und Co.
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Graphentheorie" - Cliquen und Co.
Cliquen und Co. < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Cliquen und Co.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

        
Bezug
Cliquen und Co.: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Cliquen und Co.: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
Cliquen und Co.: Antwort
Status: (Antwort) fertig Status 
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.

Bezug
                                
Bezug
Cliquen und Co.: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 17:38 Do 25.06.2009
Autor: Audience

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

Bezug
                                        
Bezug
Cliquen und Co.: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:21 Sa 27.06.2009
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]