Probleme beim Verständnis der Definition einer Clique

7

Meine Definition sagt

Eine Clique ist ein Diagramm mit einer Kante, die jedes Scheitelpunktpaar verbindet

aber wie ich verstehe, verbindet eine Kante nur zwei Eckpunkte. MögenEIN- -B..

Wenn wir drei Eckpunkte verbinden wollen, brauchen wir mindestens zwei Kanten. Zum Beispiel,EIN- -B.- -C..

Ich verstehe nicht, wie eine Kante jedes Scheitelpunktpaar verbinden kann.

Yashirq
quelle
2
Es ist nicht eine Kante edas verbindet alle Paare. Für jedes Paaru,vV. Es gibt eine Kante euvdas verbindet die beiden Knoten. Das heißt, eine Clique ist ein (Unter-) Graph, der alle möglichen Kanten enthält.
AdrianN

Antworten:

12

Daran erinnern, dass eine Clique eine Teilmenge ist C. von Eckpunkten eines ungerichteten Graphen, so dass der durch C.ist vollständig verbunden. Das heißt, alle zwei unterschiedlichen Eckpunkte inC.sind durch eine deutliche Kante des Diagramms verbunden. Dies bedeutet unterschiedliche Kanten, nicht die gleichen.

Also auf eine Clique C. enthält k Eckpunkte v1,v2,..,vk, es gibt k(k- -1)2 Kanten, die sie verbinden, das ist die Anzahl der möglichen ungeordneten Paare k Elemente.

Beispiel

Geben Sie hier die Bildbeschreibung ein

Wie Sie im vorherigen Bild sehen können, ist dies eine Clique auf vier Eckpunkten {1,2,3,4}}Es gibt also eine andere Kante, die jede Kante verbindet (dh (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)).

Sie können sie zählen und sehen, dass es genau gibt 6=4×32 Kanten.

darioSka
quelle
1
Woher wissen Sie, dass es k (k-1) / 2 Kanten gibt?
Yashirq
3
Für jeweils 2 Eckpunkte gibt es eine Kante. Wie viele Scheitelpunktpaare haben Sie?n? (n2)
Eugene