독립집합

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
파란 꼭짓점 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)라고 쓴다.[1]:3

성질[편집]

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

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

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

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

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

알고리즘[편집]

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

  • 최대 독립 집합 문제(영어: maximum independent set problem): 주어진 그래프의 (적어도 하나의) 최대 독립 집합을 찾는 문제
  • 극대 독립 집합 문제(영어: maximal independent set problem): 주어진 그래프의 (적어도 하나의) 극대 독립 집합을 찾는 문제
  • 극대 독립 집합 나열 문제: 주어진 그래프의 모든 극대 독립 집합을 찾는 문제. NP-난해 문제를 다룰 때 부분 단계로 자주 등장한다.
  • 독립 집합 결정 문제(영어: independent set decision problem): 그래프 G가 주어진 크기 k의 독립 집합을 포함하는지를 판정하는 결정 문제.

참고 문헌[편집]

  1. (영어) Godsil, Chris, Gordon Royle (2001). 《Algebraic graph theory》. New York: Springer. ISBN 0-387-95220-9

바깥 고리[편집]

같이 보기[편집]