vollständiger Teilgraph / Clique

Neue Frage »

swclhard Auf diesen Beitrag antworten »
vollständiger Teilgraph / Clique
Kann mir jemand erklären, was eine Clique ist?
Am besten am Haus vom Nikolaus, was ja jeder kennen müsste Rock !

Was muss ich also zählen, damit ich weiß, wieviele Cliquen in einem Graphen sind? Ist wahrscheinlich ganz leicht, aber ich kann mit der mathematischen Beschreibung leider nicht soviel anfangen.
JochenX Auf diesen Beitrag antworten »

Zitat:
Ist wahrscheinlich ganz leicht, aber ich kann mit der mathematischen Beschreibung leider nicht soviel anfangen.

schreib die doch einfach mal hier rein....
und sag, WAS daran nicht zu verstehen ist....

mfg jochen
 
 
swclhard Auf diesen Beitrag antworten »

Ok bei mir steht hier:

Eine Knotenmenge C Teilmenge von V heißt Clique in einem Graphen G, falls der von C induzierte Subgraph G[C] vollständig ist.

Leider kann ich aus diesem Satz nicht schließen, was eine Clique ist bzw. wie ich die jetzt in einem Graphen ausmache.

Ich verstehe nicht was mit vollstänfig genau gemeint ist. Ich habe noch keine Definition gefunden. Heißt das vieleicht abgeschlossen also ein Kreis?
JochenX Auf diesen Beitrag antworten »

weißt du, was der teilgraph ist der von C aufgespannt wird?
das ist einfach die knotenmenge C mit allen kanten aus V, die zwischen knoten aus C liegen
(schmeiße also einfach alle knoten aus V\C und die ansessigen kanten weg)

jetzt solltest du eben noch nachlesen, was vollständig heißt
Tobias Auf diesen Beitrag antworten »

Ein vollständiger Graph ist ein Graph, in dem man keine weitere Kante hinzufügen kann ohne eine Mehrfachkante bzw. Schlinge zu erzeugen. (zwischen zwei beliebigen Ecken existiert also immer eine Kante)

Eine k-Clique eines Graphen ist eine Menge von k verschiedenen Ecken, in der jede Ecke mit jeder verbunden ist. (Also ein vollständiger Teilgraph von G).

In der Skizze ist das blaue eine 3-Clique und das rote eine 4-Clique.
swclhard Auf diesen Beitrag antworten »

Ok!
Das wären dann in deiner Skizze insgesammt 7 verschiedene Cliquen oder?
JochenX Auf diesen Beitrag antworten »

alleine 2-cliquen zähle ich da schon mehr

@tobi: sind eigentlich alle einzelnen knoten cliquen? nach definition ja schon
swclhard Auf diesen Beitrag antworten »

Also bei dem Angehängten Bild steht Cliquenzahl d=4?

Wer erklärt mir das?

Kann mir auch mal einer sagen, wie ich eine Skizze anhänge?
JochenX Auf diesen Beitrag antworten »

welches angehängte bild? wer erklärt uns DAS?
bei tobi zumindest stehts nicht
wie kommst du bei ihm auf 7?
ich zähle z.b. 1 viererclique und 5 dreiercliquen


edit: ach so, einfach als jpg unten bei "Dateianhang:" (wenn du postest unter deinem text) speichern
swclhard Auf diesen Beitrag antworten »

Nein Sorry! Die Lösung zu dem Bild was ich anhängen wollte wäre d=4.

Und bei Tobi zähle ich eine 4-Clique (rot), in ihr dann nochmal 4 3-Cliquen, dann noch eine 4-Clique rechts unten und die 3-Clique (blau oben)
Macht bei mir 6

Das bei Tobi wäre dann geklärt. Stellt sich die Frage zu der Lösung meiner Skizze. Warum 4? Ich zähle eine 4-Clique und 4 3 Cliquen. Oder Zählt man nur die Cliquen, die minimal sind, also nicht die 4-Clique
AD Auf diesen Beitrag antworten »

Zitat:
Original von swclhard
dann noch eine 4-Clique rechts unten

Da ist keine!
JochenX Auf diesen Beitrag antworten »

Zitat:
Und bei Tobi zähle ich eine 4-Clique (rot), in ihr dann nochmal 4 3-Cliquen, dann noch eine 4-Clique rechts unten und die 3-Clique (blau oben)
Macht bei mir 6

also nach deiner zählung wären es 7 1+4+1+1
aber das rechts ist keine 4-clique, davon gibts nur eine

bei deinem gibt es tatsächlich 4 3cliquen und eine 4clique, also mindestens 5 cliquen
bist du sicher, dass nicht nach der anzahl der 3knotigen cliquen gefragt ist?


aber wo steht denn in der definition, dass nicht auch 2 oder 1 punkt(e) eine clique bilden?
swclhard Auf diesen Beitrag antworten »

Mh ja dann hab mich bei tobi verzählt! Würde nach meiner Zählung also 7 sein.
Und das unten rechts keine clique ist sehe ich ein, da man ja die jeweils gegenüberliegenden Knoten noch mit ner Kante verbinden kann. Also wären das bei Tob 6 Cliquen.

Und bei meinem Graphen: Es ist nur der Graph aufgezeichnet mit der Erläuterung: n=8 Knoten, m=9 Kanten c=2 Zusammenhangskomponenten, Cliquenzahl d=4, Unabhängigkeitszahl alpha=3. Maximalgrad 4, Minimalgrad 1, Graph mit Knoten 1 bis 6 hat Radius 2 und Durchmesser 3. G ist planar aber in keiner planaren Einbettung
Tobias Auf diesen Beitrag antworten »

Also streng nach Definition ist auch ein isolierter Knoten eine Clique.

Die "Cliquenzahl" ist aber ein verhängnisvolles Wort, denn gemeint ist nicht die Anzahl der Cliquen in einem Graphen sondern die Kardinalität der größten Clique. In deinem Fall 4, weil der größte vollständige Untergraph 4 Ecken hat.
JochenX Auf diesen Beitrag antworten »

Zitat:
Original von Tobias
Also streng nach Definition ist auch ein isolierter Knoten eine Clique.

danke

info1-gruß an dich
Wink und Mit Zunge
swclhard Auf diesen Beitrag antworten »

Ok dann hat sich das geklärt mit der 4.
Aber mal abgesehen davon.. Wieviele cliquen gibts denn nun in meinem Graphen?
1. 2,3,4,5
2. 2,3,4
3. 3,4,5
4. 4,5,2
5. 5,2,3
6. 7,8
JochenX Auf diesen Beitrag antworten »

22 stück gibt's

du hast viele andere 2ercliquen und alle einsercliquen vergessen
Tobias Auf diesen Beitrag antworten »

Zitat:
Original von LOED
info1-gruß an dich


Ich weiß du willst es nicht wahr haben, aber Graphentheorie ist Mathematik. Augenzwinkern

Ich komme auch auf 22 Stück:

1er: 8 (Anzahl Ecken)
2er: 9 (Anzahl Kanten)
3er: 4 (Anzahl Dreiecke)
4er: 1
Neue Frage »
Antworten »



Verwandte Themen

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