Mi definición dice
A clique es un gráfico que tiene un borde que conecta cada par de vértices
pero según tengo entendido, un borde conecta solo dos vértices. Como $ A-B $ .
Si queremos conectar tres vértices, necesitamos al menos dos aristas. Por ejemplo, $ ABC $ .
No entiendo cómo una arista puede conectar cada par de vértices.
Comentarios
- No es ' un borde $ e $ que conecte todos los pares. Para cada par $ u, v \ en V $ hay un borde $ e_ {uv} $ que conecta los dos nodos. Es decir, una camarilla es un (sub) gráfico que contiene todos los bordes posibles.
Respuesta
Recordando que una camarilla es un subconjunto $ C $ de vértices de un gráfico no dirigido, tal que el subgrafo inducido por $ C $ está completamente conectado. Es decir, cada dos vértices distintos en $ C $ están conectados por un borde distinto del gráfico. Esto significa bordes diferentes, no iguales.
Entonces, en una camarilla $ C $ que contiene $ k $ vértices $ v_1, v_2, .., v_k $ , hay $ \ frac {k (k-1) } 2 $ bordes que los conectan, es decir, el número de posibles pares desordenados en elementos $ k $ .
Ejemplo
Como puede ver en la anterior imagen, esta es una camarilla en cuatro vértices $ \ {{1,2,3,4} \} $ , por lo que hay una arista diferente que conecta cada arista (es decir $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Puede contarlos y ver que hay exactamente $ 6 = \ frac {4 \ times 3} {2} $ bordes.
Comentarios
- ¿Cómo sabe que hay k (k-1) / 2 aristas?
- Por cada 2 vértices hay una arista. ¿Cuántos pares de vértices tienes de $ n $? $ \ binom {n} {2} $