독립집합

파란 꼭짓점 9개가 극대 독립집합을 나타낸다. 이 그래프의 꼭짓점은 모두 24개이다.

그래프 이론에서 독립 집합(獨立集合, 영어: independent set)은 서로 인접하지 않는 꼭짓점들의 집합이다.

정의

정육면체의 그래프는 총 6개의 극대 독립 집합을 갖는다. 이들 가운데, 두 개(가운데 열)는 최대 독립 집합이다.

그래프 $G$의 독립집합 $I\subset V(G)$는 다음 성질을 만족시키는 집합이다.

• 모든 $u,v\in I$에 대하여, $uv\not \in E(G)$

그래프 $G$의 독립 집합들의 집합은 포함 관계에 따라서 부분 순서 집합을 이룬다. 극대 독립 집합(영어: maximal independent set)은 포함 관계에 따라서 최대인 독립 집합이다.

최대 독립 집합(영어: maximum independent set)은 그래프 G에 대해서 꼭짓점 수가 최대인 독립 집합이다. 그래프 $G$의 최대 독립집합의 크기는 $\alpha (G)$라고 쓴다.^:3

성질

그래프의 극대 독립 집합은 우세 집합(영어: dominating set)이다. 그래프 $G$의 극대 독립 집합의 수는 $3^{|E(G)|/3}$ 이하이다.

다른 그래프 특성과 관계

어떤 집합이 독립 집합인 것은 그 그래프의 여 그래프에서 그 집합이 클릭을 이루는 것과 동치이다. 따라서 독립 집합과 클릭은 상호 보완 관계이다. 큰 클릭이 없고 충분히 큰 그래프에는 큰 독립 집합이 있다는 것이 램지 이론에서 연구하는 주제이다.

어떤 집합이 독립 집합인 것은 여집합이 꼭짓점 덮개인 것과 동치이다. $\alpha (G)$와 최소 꼭짓점 덮개 $\beta (G)$의 합은 그래프의 꼭짓점 수가 된다.

이분 그래프에서는 최대 독립 집합의 크기와 최소 변 덮개의 크기가 같다.

알고리즘

독립 집합과 관련된 문제로는 다음을 들 수 있다.

• 최대 독립 집합 문제(영어: maximum independent set problem): 주어진 그래프의 (적어도 하나의) 최대 독립 집합을 찾는 문제
  • 이 문제는 NP-난해 최적화 문제이다.
• 극대 독립 집합 문제(영어: maximal independent set problem): 주어진 그래프의 (적어도 하나의) 극대 독립 집합을 찾는 문제
  • 이 문제는 다항 시간에 간단한 탐욕 알고리즘으로 풀 수 있다.
• 극대 독립 집합 나열 문제: 주어진 그래프의 모든 극대 독립 집합을 찾는 문제. NP-난해 문제를 다룰 때 부분 단계로 자주 등장한다.
• 독립 집합 결정 문제(영어: independent set decision problem): 그래프 $G$가 주어진 크기 $k$의 독립 집합을 포함하는지를 판정하는 결정 문제.
  • 이는 그 여 그래프의 클릭 문제와 동치이며, NP-완전 문제이다.

외부 링크

• Weisstein, Eric Wolfgang. “Maximal independent vertex set”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring Archived 2013년 5월 29일 - 웨이백 머신

같이 보기

• 부합