독립집합 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:Independent set graph.svg|섬네일|파란 꼭짓점 9개가 극대 독립집합을 나타낸다. 이 그래프의 꼭짓점은 모두 24개이다.]]

[[그래프 이론]]에서 '''독립 집합'''(獨立集合, {{llang|en|independent set}})은 서로 인접하지 않는 꼭짓점들의 집합이다.

== 정의 ==
[[파일:Cube-maximal-independence.svg|섬네일|오른쪽|[[정육면체]]의 그래프는 총 6개의 극대 독립 집합을 갖는다. 이들 가운데, 두 개(가운데 열)는 최대 독립 집합이다.]]
[[그래프]] <math>G</math>의 '''독립집합''' <math>I\subset V(G)</math>는 다음 성질을 만족시키는 집합이다.
* 모든 <math>u,v\in I</math>에 대하여, <math>uv\not\in E(G)</math>
그래프 <math>G</math>의 독립 집합들의 집합은 포함 관계에 따라서 [[부분 순서 집합]]을 이룬다. '''극대 독립 집합'''({{llang|en|maximal independent set}})은 포함 관계에 따라서 최대인 독립 집합이다.

'''최대 독립 집합'''({{llang|en|maximum independent set}})은 그래프 G에 대해서 꼭짓점 수가 최대인 독립 집합이다. 그래프 <math>G</math>의 최대 독립집합의 크기는 <math>\alpha(G)</math>라고 쓴다.<ref>{{서적 인용
  | 성 = Godsil
  | 이름 = Chris
  | 공저자 = Gordon Royle
  | 제목 = Algebraic graph theory
  | 출판사 = Springer
  | 연도 = 2001
  | 출판위치=New York
  | isbn = 0-387-95220-9 | 언어=en }}</ref>{{rp|3}}

== 성질 ==
그래프의 극대 독립 집합은 [[우세 집합]]({{llang|en|dominating set}})이다. 그래프 <math>G</math>의 극대 독립 집합의 수는 <math>3^{|E(G)|/3}</math> 이하이다.

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

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

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

=== 알고리즘 ===
독립 집합과 관련된 문제로는 다음을 들 수 있다.
* '''최대 독립 집합 문제'''({{llang|en|maximum independent set problem}}): 주어진 [[그래프]]의 (적어도 하나의) 최대 독립 집합을 찾는 문제
** 이 문제는 [[NP-난해]] [[최적화 문제]]이다.
* '''극대 독립 집합 문제'''({{llang|en|maximal independent set problem}}): 주어진 [[그래프]]의 (적어도 하나의) 극대 독립 집합을 찾는 문제
** 이 문제는 [[다항 시간]]에 간단한 [[탐욕 알고리즘]]으로 풀 수 있다.
* '''극대 독립 집합 나열 문제''': 주어진 [[그래프]]의 모든 극대 독립 집합을 찾는 문제. [[NP-난해]] 문제를 다룰 때 부분 단계로 자주 등장한다.
* '''독립 집합 결정 문제'''({{llang|en|independent set decision problem}}): [[그래프]] <math>G</math>가 주어진 크기 <math>k</math>의 독립 집합을 포함하는지를 판정하는 [[결정 문제]].
** 이는 그 [[여 그래프]]의 [[클릭 (그래프 이론)|클릭]] 문제와 동치이며, [[NP-완전]] 문제이다.

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|title=Maximal independent vertex set|id=MaximalIndependentVertexSet}}
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring] {{웹아카이브|url=https://web.archive.org/web/20130529163947/http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm}}

== 같이 보기 ==
* [[부합 (그래프 이론)|부합]]

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