Minha definição diz
A clique é um gráfico que tem uma aresta conectando cada par de vértices
mas pelo que entendi, uma aresta conecta apenas dois vértices. Como $ A-B $ .
Se quisermos conectar três vértices, precisamos de pelo menos duas arestas. Por exemplo, $ ABC $ .
Não entendo como uma aresta pode conectar cada par de vértices.
Comentários
- Ele ' não é uma borda $ e $ que conecta todos os pares. Para cada par $ u, v \ em V $ existe uma aresta $ e_ {uv} $ que conecta os dois nós. Ou seja, um clique é um (sub-) grafo que contém todas as arestas possíveis.
Resposta
Lembrando que um clique é um subconjunto $ C $ de vértices de um grafo não direcionado tal que o subgrafo induzido por $ C $ está totalmente conectado. Ou seja, cada dois vértices distintos em $ C $ são conectados por uma aresta distinta do gráfico. Isso significa arestas diferentes, não iguais.
Então, em um clique $ C $ contendo $ k $ vértices $ v_1, v_2, .., v_k $ , existem $ \ frac {k (k-1) } 2 $ arestas conectando-os, ou seja, o número de pares possíveis não ordenados em elementos $ k $ .
Exemplo
Como você pode ver no anterior imagem, este é um clique em quatro vértices $ \ {{1,2,3,4} \} $ , então há uma aresta diferente conectando cada aresta (ou seja $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Você pode contá-los e ver que há exatamente $ 6 = \ frac {4 \ times 3} {2} $ bordas.
Comentários
- Como você sabe que existem k (k-1) / 2 arestas?
- Para cada 2 vértices há uma aresta. Quantos pares de vértices você tem de $ n $? $ \ binom {n} {2} $