Tendo problemas para entender a definição de clique

Minha definição diz

Uma clique é um gráfico que possui uma aresta conectando todos os pares de vértices

mas, pelo que entendi, uma aresta conecta apenas dois vértices. Como . $A-B$

Se queremos conectar três vértices, precisamos de pelo menos duas arestas. Por exemplo, . $A-B-C$

Não entendo como uma aresta pode conectar todos os pares de vértices.

graphs graph-theory clique yashirq
fonte

Não é uma extremidade

e

$e$ que conecta todos os pares. Para cada par

u, v \in V

$u,v\in V$ existe uma aresta

e_{u v}

$e_{uv}$ que conecta os dois nós. Ou seja, uma clique é um (sub-) gráfico que contém todas as arestas possíveis.

Adriann

Respostas:

Lembrando que uma clique é um subconjunto $C$ de vértices de um gráfico não direcionado, de modo que o subgrafo induzido por $C$ esteja totalmente conectado. Ou seja, todos os dois vértices distintos em $C$ são conectados por uma aresta distinta do gráfico. Isso significa arestas diferentes, não iguais.

Portanto, em um clique contendo vértices , há arestas conectando-os, que é o número de possíveis pares não ordenados em elementos. $C$ $k$ $v_1, v_2,..,v_k$ $\frac{k(k-1)}2$ $k$

Exemplo

Como você pode ver na figura anterior, este é um clique em quatro vértices ; portanto, existe uma aresta diferente conectando todas as arestas (por exemplo, , , , , , ). $\{{1,2,3,4}\}$ $(1,2)$ $(1,3)$ $(1,4)$ $(2,3)$ $(2,4)$ $(3,4)$

Você pode contá-los e ver se existem exatamente arestas. $6 = \frac{4\times 3}{2}$

darioSka
fonte

Como você sabe que existem k (k-1) / 2 arestas?

yashirq

Para cada 2 vértices, há uma aresta. Quantos pares de vértices você possui de ?

n

$n$

(\binom{n}{2})

$\binom{n}{2}$

Eugene