독립집합

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

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

정의[원본 편집]

정육면체의 그래프는 총 6개의 극대 독립 집합을 갖는다. 이들 가운데, 두 개(가운데 열)는 최대 독립 집합이다.

그래프 독립집합 는 다음 성질을 만족시키는 집합이다.

  • 모든 에 대하여,

그래프 의 독립 집합들의 집합은 포함 관계에 따라서 부분 순서 집합을 이룬다. 극대 독립 집합(영어: maximal independent set)은 포함 관계에 따라서 최대인 독립 집합이다.

최대 독립 집합(영어: maximum independent set)은 그래프 G에 대해서 꼭짓점 수가 최대인 독립 집합이다. 그래프 의 최대 독립집합의 크기는 라고 쓴다.[1]:3

성질[원본 편집]

그래프의 극대 독립 집합은 우세 집합(영어: dominating set)이다. 그래프 의 극대 독립 집합의 수는 이하이다.

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

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

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

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

알고리즘[원본 편집]

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

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

참고 문헌[원본 편집]

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

바깥 고리[원본 편집]

같이 보기[원본 편집]