Meine Definition lautet
A. Clique ist ein Graph mit einer Kante, die jedes Scheitelpunktpaar verbindet.
Aber wie ich verstehe, verbindet eine Kante nur zwei Scheitelpunkte. Wie $ A-B $ .
Wenn wir drei Eckpunkte verbinden möchten, benötigen wir mindestens zwei Kanten. Beispiel: $ ABC $ .
Ich verstehe nicht, wie eine Kante jedes Scheitelpunktpaar verbinden kann.
Kommentare
- ' ist nicht eine Kante $ e $, die alle Paare verbindet. Für jedes Paar $ u, v \ In V $ gibt es eine Kante $ e_ {uv} $, die die beiden Knoten verbindet. Das heißt, eine Clique ist ein (Unter-) Graph, der alle möglichen Kanten enthält.
Antwort
Unter Hinweis darauf, dass eine Clique eine Teilmenge $ C $ von Eckpunkten eines ungerichteten Graphen ist, so dass Der durch $ C $ induzierte Untergraph ist vollständig verbunden. Das heißt, alle zwei unterschiedlichen Eckpunkte in $ C $ sind durch eine eindeutige Kante des Diagramms verbunden. Dies bedeutet unterschiedliche Kanten, nicht die gleichen.
Also, auf einer Clique $ C $ , die $ k $ vertices $ v_1, v_2, .., v_k $ , es gibt $ \ frac {k (k-1) } 2 $ Kanten, die sie verbinden, dh die Anzahl der möglichen ungeordneten Paare auf $ k $ -Elementen.
Beispiel
Wie Sie im vorherigen sehen können Bild, dies ist eine Clique auf vier Eckpunkten $ \ {{1,2,3,4} \} $ , so dass es eine andere Kante gibt, 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 welche gibt $ 6 = \ frac {4 \ times 3} {2} $ Kanten.
Kommentare
- Woher wissen Sie, dass es k (k-1) / 2 Kanten gibt?
- Für jeweils 2 Eckpunkte gibt es eine Kante. Wie viele Eckpunktpaare haben Sie von $ n $? $ \ binom {n} {2} $