독립집합

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

 정의 
섬네일|오른쪽|정육면체의 그래프는 총 6개의 극대 독립 집합을 갖는다. 이들 가운데, 두 개(가운데 열)는 최대 독립 집합이다.
그래프 의 독립집합 는 다음 성질을 만족시키는 집합이다.
 모든 에 대하여, 
그래프 의 독립 집합들의 집합은 포함 관계에 따라서 부분 순서 집합을 이룬다. 극대 독립 집합()은 포함 관계에 따라서 최대인 독립 집합이다.

최대 독립 집합()은 그래프 G에 대해서 꼭짓점 수가 최대인 독립 집합이다. 그래프 의 최대 독립집합의 크기는 라고 쓴다.

 성질 
그래프의 극대 독립 집합은 우세 집합()이다. 그래프 의 극대 독립 집합의 수는  이하이다.

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

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

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

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

 참고 문헌 

 외부 링크 

 Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring 

 같이 보기 
 부합

분류:그래프 이론의 계산 문제
분류:NP-완전 문제