전체 그래프에서 최소 정점 커버리지의 카디널리티는 무엇입니까?

Question

나는 꼭지점이 n 인 완전한 그래프를 가지고있다. 완전한 그래프의 MinimumVertexCover 내가 MinimumVertexCover으로 N-1 적은 다음을 N-1 .Can입니까? 대답이 이면입니다. 설명과 함께 설명해주십시오.

Answer 1

대답은 나는 그것이 Gallai의 결과에 의해 증명하는 가장 쉬운 방법을 생각 번호

입니다. 독립적 인 꼭지점 집합은 두 꼭지점이 모서리를 공유하는 점입니다. 이제 Gallai의 정리는 말한다 :

α (G) + β (G) = N

,

α (G) = 최대의 독립 세트의 크기, β (G) = 크기 최소 정점 커버하고 N = 의 KN 두 꼭지점 집합 보낸 G.

정점

지금 분명 (KN)를 α = 1의

수는 독립적이 아니다. 따라서, 필요에 따라 β (G) = n-1이된다.