Ma définition dit
A clique est un graphe qui a une arête reliant chaque paire de sommets
mais si je comprends bien, une arête ne relie que deux sommets. Comme $ A-B $ .
Si nous voulons relier trois sommets, nous avons besoin dau moins deux arêtes. Par exemple, $ ABC $ .
Je ne comprends pas comment une arête peut connecter chaque paire de sommets.
Commentaires
- Il ' nest pas un bord $ e $ qui relie toutes les paires. Pour chaque paire $ u, v \ dans V $ il y a une arête $ e_ {uv} $ qui relie les deux nœuds. Autrement dit, une clique est un (sous-) graphe qui contient toutes les arêtes possibles.
Réponse
Rappelant quune clique est un sous-ensemble $ C $ de sommets dun graphe non orienté tel que le sous-graphe induit par $ C $ est entièrement connecté. Autrement dit, tous les deux sommets distincts dans $ C $ sont reliés par un bord distinct du graphique. Cela signifie des arêtes différentes, pas les mêmes.
Donc, sur une clique $ C $ contenant $ k $ sommets $ v_1, v_2, .., v_k $ , il y a $ \ frac {k (k-1) } 2 $ arêtes les reliant, cest-à-dire le nombre de paires non ordonnées possibles sur les éléments $ k $ .
Exemple
Comme vous pouvez le voir dans le précédent image, ceci est une clique sur quatre sommets $ \ {{1,2,3,4} \} $ , donc il y a une arête différente reliant chaque arête (ie $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
Vous pouvez les compter et voir quil y en a exactement $ 6 = \ frac {4 \ fois 3} {2} $ bords.
Commentaires
- Comment savez-vous quil y a k (k-1) / 2 arêtes?
- Pour tous les 2 sommets, il y a une arête. Combien de paires de sommets avez-vous de $ n $? $ \ binom {n} {2} $