독립집합

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

그래프 ${\displaystyle G}$의 독립집합 ${\displaystyle I\subset V(G)}$는 다음 성질을 만족시키는 집합이다.

• 모든 ${\displaystyle u,v\in I}$에 대하여, ${\displaystyle uv\not \in E(G)}$

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

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

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

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

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

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

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

• 최대 독립 집합 문제(영어: maximum independent set problem): 주어진 그래프의 (적어도 하나의) 최대 독립 집합을 찾는 문제
  • 이 문제는 NP-난해 최적화 문제이다.
• 극대 독립 집합 문제(영어: maximal independent set problem): 주어진 그래프의 (적어도 하나의) 극대 독립 집합을 찾는 문제
  • 이 문제는 다항 시간에 간단한 탐욕 알고리즘으로 풀 수 있다.
• 극대 독립 집합 나열 문제: 주어진 그래프의 모든 극대 독립 집합을 찾는 문제. NP-난해 문제를 다룰 때 부분 단계로 자주 등장한다.
• 독립 집합 결정 문제(영어: independent set decision problem): 그래프 ${\displaystyle G}$가 주어진 크기 ${\displaystyle k}$의 독립 집합을 포함하는지를 판정하는 결정 문제.
  • 이는 그 여 그래프의 클릭 문제와 동치이며, NP-완전 문제이다.

• Weisstein, Eric Wolfgang. “Maximal independent vertex set”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring Archived 2013년 5월 29일 - 웨이백 머신

• 부합