Moja definicja brzmi
A clique to wykres, którego krawędź łączy każdą parę wierzchołków
ale jak rozumiem, krawędź łączy tylko dwa wierzchołki. Na przykład $ A-B $ .
Jeśli chcemy połączyć trzy wierzchołki, potrzebujemy co najmniej dwóch krawędzi. Na przykład $ ABC $ .
Nie rozumiem, jak krawędź może łączyć każdą parę wierzchołków.
Komentarze
- To ' to nie jedna krawędź $ e $ łącząca wszystkie pary. Dla każdej pary $ u, v \ w V $ jest krawędź $ e_ {uv} $, która łączy dwa węzły. Oznacza to, że klika to (pod-) wykres zawierający wszystkie możliwe krawędzie.
Odpowiedź
Przypominając sobie, że klika jest podzbiorem $ C $ wierzchołków niekierowanego grafu, tak że podgraf wywołany przez $ C $ jest w pełni połączony. Oznacza to, że każde dwa odrębne wierzchołki w $ C $ są połączone wyraźną krawędzią wykresu. Oznacza to różne krawędzie, a nie to samo.
Tak więc w kliku $ C $ zawierającym $ k $ wierzchołki $ v_1, v_2, .., v_k $ , istnieją $ \ frac {k (k-1) } 2 $ krawędzi łączących je, czyli liczba możliwych nieuporządkowanych par na $ k $ elementach.
Przykład
Jak widać w poprzednim obrazek, to jest klika na czterech wierzchołkach $ \ {{1,2,3,4} \} $ , więc istnieje inna krawędź łącząca każdą krawędź (tj. $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Możesz je policzyć i zobaczyć, że są dokładnie $ 6 = \ frac {4 \ times 3} {2} $ brzegi.
Komentarze
- Skąd wiesz, że istnieje k (k-1) / 2 krawędzi?
- Na każde 2 wierzchołki przypada krawędź. Ile masz par wierzchołków z $ n $? $ \ binom {n} {2} $