독립집합

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
파란 꼭지점 9개가 극대 독립집합을 나타낸다. 이 그래프의 꼭지점은 모두 24개이다.

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

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

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

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

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

성질[편집]

다른 그래프 특성과 관계[편집]

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

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

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

극대 독립집합[편집]

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

더 보기[편집]

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

주석[편집]

  1. Godsil & Royle 2004, p.3

참고문헌[편집]

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

바깥 연결[편집]