내 정의에 따르면
A clique는 모든 정점 쌍을 연결하는 가장자리가있는 그래프입니다.
하지만 제가 이해했듯이 가장자리는 두 정점 만 연결합니다. $ A-B $ 와 같습니다.
3 개의 꼭지점을 연결하려면 최소 2 개의 가장자리가 필요합니다. 예 : $ ABC $ .
나는 가장자리가 모든 정점 쌍을 연결하는 방법을 이해하지 못합니다.
설명
- ' 모든 쌍을 연결하는 하나의 에지 $ e $가 아닙니다. 각 쌍에 대해 $ u, v \ V $에는 두 노드를 연결하는 $ e_ {uv} $ 에지가 있습니다. 즉, 파벌은 가능한 모든 에지를 포함하는 (서브) 그래프입니다.
Answer
파벌이 무 방향 그래프 정점의 하위 집합 $ C $ 임을 상기하면 $ C $ 에 의해 유도 된 하위 그래프는 완전히 연결되어 있습니다. 즉, $ C $ 에있는 두 개의 서로 다른 꼭짓점마다 그래프의 고유 한 가장자리 로 연결됩니다. 즉, 동일하지 않은 다른 가장자리를 의미합니다.
따라서 $ k $ 를 포함하는 파벌 $ C $ 에서 span> 정점 $ v_1, v_2, .., v_k $ , $ \ frac {k (k-1) 이들을 연결하는} 2 $ 가장자리, 즉 $ k $ 요소에서 가능한 순서없는 쌍의 수입니다.
예
이전에서 볼 수 있듯이 그림, 이것은 네 개의 꼭지점 $ \ {{1,2,3,4} \} $ 의 파벌이므로 모든 가장자리를 연결하는 다른 가장자리가 있습니다 (예 : $ (1,2) $ , $ (1,3) $ , $ (1,4) $ , $ (2,3) $ , $ ( 2,4) $ , $ (3,4) $ ).
세어보고 정확히 $ 6 = \ frac {4 \ times 3} {2} $ 가장자리.
댓글
- k (k-1) / 2 개의 가장자리가 있는지 어떻게 알 수 있나요?
- 2 개의 꼭지점마다 가장자리가 있습니다. $ n $에서 몇 쌍의 정점이 있습니까? $ \ binom {n} {2} $