독립집합

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

그래프 이론에서 독립집합 또는 안정집합은 한 그래프에 있는 꼭지점 (그래프 이론)들의 집합으로 어떤 두 꼭지점도 서로 인접하지 않는 것을 말한다. 즉, 꼭지점 집합 V에 있는 두 꼭지점을 연결하는 변이 존재하지 않는다. 이는 그래프상의 모든 변이 V의 꼭지점에 최대 한 개만 인접하는 것과 동치이다. 독립집합의 크기는 집합에 속하는 꼭지점 개수이다.

극대 독립집합은 꼭지점을 추가하면 집합 내의 두 꼭지점을 연결하는 변이 생기게 되는 독립집합이다.

최대 독립집합은 그래프 G에 대해서 꼭지점 수가 최대인 독립집합으로, 집합의 크기를 $\alpha(G)$로 나타낸다. 최대 독립집합을 찾는 문제를 독립집합 문제라고 하는데 이는 NP-완전 문제이다. 그러한 문제를 효율적으로 푸는 알고리즘은 존재하지 않는다는 것이 전산학계의 정설이다.

독립집합 문제는 그래프에 특정 크기의 독립집합이 존재하는지를 판정하는 결정 문제로 볼 수도 있다. 이는 계산 관점에서 어떤 그래프에 특정 크기의 클릭이 존재하는지를 판정하는 것과 동등한 문제이다. 어떤 그래프에 크기 k인 독립집합이 있으면 그 그래프의 여그래프(꼭지점 집합은 갖고 변의 집합이 반대로(여집합으로) 된 그래프)에는 크기 k인 클릭이 존재한다. 독립집합 문제의 결정 문제판도 NP-완전임이 알려져 있다.

최대 독립집합과 극대 독립집합을 혼동하면 안 된다. 극대 독립집합은 어떤 다른 독립집합의 부분집합이 되지 않는 독립집합이고, 최대 독립집합은 극대 독립집합 중 크기가 가장 큰 것이다. 극대 독립집합을 찾는 문제는 다항 시간에 자명한 그리디 알고리즘으로 풀 수 있다.

성질

다른 그래프 특성과 관계

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

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

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

극대 독립집합

이 부분의 본문은 극대 독립집합입니다.

다른 독립집합의 부분집합이 아닌 독립집합을 극대 독립집합이라 한다. 그러한 집합은 우세 집합이 된다. 그래프에는 극대 독립집합이 최대 $3^{n / 3}$개 있을 수 있으나 보통은 그보다 훨씬 적다. 극대 독립집합을 늘어놓는 문제는 NP-난해 문제를 다룰 때 서브루틴으로 자주 등장한다.

더 보기

• 꼭지점이 아닌 변의 독립집합은 공유하는 꼭지점이 없는 변의 집합이다. 이를 매칭이라 한다.

참고문헌

• Godsil, Chris, Gordon Royle (2001). 《Algebraic Graph Theory》. New York: Springer. ISBN 0-387-95220-9

바깥 연결

• http://mathworld.wolfram.com/MaximalIndependentVertexSet.html
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring