독립집합

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 성질
- 3.1. 다른 그래프 특성과의 관계
- 3.2. 극대 독립 집합
4. 알고리즘
5. 독립 집합의 개수 계산
6. 응용
참조

1. 개요

독립 집합은 그래프 이론에서 사용되는 개념으로, 그래프 내에서 서로 인접하지 않은 정점들의 집합을 의미한다. 극대 독립 집합은 포함 관계에 대해 최대인 독립 집합이며, 최대 독립 집합은 정점 수가 가장 많은 독립 집합을 의미한다. 독립 집합과 관련된 문제들은 컴퓨터 과학에서 다양한 알고리즘으로 연구되며, 최대 독립 집합 문제는 NP-난해 문제로 알려져 있다. 독립 집합 결정 문제 역시 NP-완전 문제이며, 근사 알고리즘을 통해 해결할 수 있는 경우도 있다. 독립 집합은 계산 복잡도 이론 증명, 유전 시스템 설계 등 다양한 분야에 응용된다.

더 읽어볼만한 페이지

그래프 이론의 계산 문제 - 외판원 문제
외판원 문제(TSP)는 여러 도시를 모두 한 번씩 방문하고 출발점으로 돌아오는 최소 비용의 이동 순서를 구하는 문제로, NP-난해 문제에 속하며, 배송 계획 등에 응용되고 다양한 해법이 존재한다.
그래프 이론의 계산 문제 - 해밀턴 경로
해밀턴 경로는 그래프의 모든 꼭짓점을 한 번씩 방문하는 경로로, 해밀턴 순환은 이러한 경로가 순환 형태를 띠는 것을 의미하며, 이들은 그래프 이론에서 중요한 개념으로 NP-완전 문제 및 외판원 문제 등에 응용된다.
NP-완전 문제 - 지뢰 찾기
지뢰 찾기는 격자 형태 지뢰밭에서 지뢰를 피해 안전한 칸을 모두 여는 퍼즐 비디오 게임으로, 칸을 열어 지뢰 유무를 확인하며, 윈도우 탑재를 통해 대중화되었고 NP-완전 문제로 분류된다.
NP-완전 문제 - 스도쿠
스도쿠는 9x9 칸에 1부터 9까지의 숫자를 채워 넣는 퍼즐로, 각 가로줄, 세로줄, 3x3 칸에 숫자가 중복 없이 들어가야 하며, 레온하르트 오일러의 라틴 방진을 기반으로 다양한 변형과 응용 연구가 진행되고 있다.

독립집합
개요
정의	그래프 이론에서 독립 집합(Independent Set)은 그래프 내에서 서로 인접하지 않은 정점들의 집합을 의미한다. 즉, 집합 내의 어떤 두 정점도 변으로 연결되어 있지 않다.
동의어	안정 집합(Stable Set)
속성
최대 독립 집합	그래프에서 가장 큰 독립 집합의 크기를 의미하며, 독립수(Independence Number)라고도 한다.
클리크와의 관계	그래프 G의 독립 집합은 G의 여 그래프(Complement Graph)에서 클리크(Clique)를 형성한다.
정점 커버와의 관계	그래프 G의 독립 집합 I는 G의 정점 커버(Vertex Cover) V - I에 해당한다. 여기서 V는 G의 모든 정점 집합이다.
문제
최대 독립 집합 문제	주어진 그래프에서 최대 크기의 독립 집합을 찾는 문제이다. NP-완전 문제에 속한다.
독립 집합 판별 문제	주어진 그래프에서 특정 크기 이상의 독립 집합이 존재하는지 판별하는 문제이다. 역시 NP-완전 문제이다.
알고리즘 및 복잡도
일반적인 그래프	일반적인 그래프에서 최대 독립 집합을 찾는 문제는 NP-hard이다.
특수한 그래프	이분 그래프: 이분 그래프에서는 최대 독립 집합을 다항 시간 내에 찾을 수 있다. 현 그래프: 현 그래프에서도 최대 독립 집합을 다항 시간 내에 찾을 수 있다.
응용
스케줄링	서로 충돌하는 작업들을 그래프로 모델링하고, 독립 집합을 찾아 동시에 수행 가능한 작업 집합을 결정할 수 있다.
코드 최적화	프로그램 코드에서 서로 간섭하지 않는 명령어들을 찾아 동시에 실행하여 성능을 향상시킬 수 있다.
소셜 네트워크 분석	소셜 네트워크에서 서로 연결되지 않은 사용자 그룹을 찾아 특정 정보가 전파되지 않도록 차단하거나, 영향력 있는 사용자 그룹을 식별할 수 있다.
참고 문헌
참고 문헌 목록	Korshunov, A. D. (1974). Solution of a problem of Erdös and Rényi on the maximal cardinality of families of subsets of a finite set in which no set is contained in the union of the others. Discrete Mathematics, 23(3), 207–216. Godsil, C., & Royle, G. (2001). Algebraic Graph Theory. Springer. Garey, M. R., & Johnson, D. S. (1978). "Strong" NP-Completeness Results: Motivation, Examples, and Implications. Journal of the ACM, 25(3), 499–508.

2. 정의

그래프 $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)

라고 쓴다.^[32]

3. 성질

극대 독립 집합은 지배 집합(우세 집합)이다.^[5] 그래프의 극대 독립 집합의 개수는 최대 3^|E(G)|/3개이다.^[5]

''n''-정점 사이클 그래프의 극대 독립 집합의 개수는 페린 수열로 주어지며, ''n''-정점 경로 그래프의 극대 독립 집합의 개수는 파도반 수열로 주어진다.^[6]^[31] 이 두 수열은 모두 플라스틱 수 1.324718...의 거듭제곱에 비례한다.

3. 1. 다른 그래프 특성과의 관계

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

어떤 집합이 독립 집합인 것은 그 여집합이 정점 덮개인 것과 동치이다.^[4] 따라서 최대 독립 집합의 크기

\alpha(G)

와 최소 정점 덮개의 크기

\beta(G)

의 합은 그래프의 정점 수와 같다.

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

그래프의 정점 채색은 정점 집합을 독립 부분 집합으로 분할하는 것과 같다. 따라서 정점 채색에 필요한 최소 색상 수인 ''채색수''

\chi(G)

는 그래프의 정점 수와 독립수

\alpha(G)

의 몫 이상이다.

3. 2. 극대 독립 집합

다른 독립 집합의 진부분집합이 아닌 독립 집합을 '''극대 독립 집합'''이라고 부른다. 이러한 집합은 지배 집합이기도 하다. 모든 그래프는 최대 3^''n''/3개의 극대 독립 집합을 포함하지만,^[5] 실제로는 그보다 훨씬 적은 개수를 갖는 경우가 많다.

''n''개의 정점을 가진 사이클 그래프에서 극대 독립 집합의 개수는 페린 수열로 주어지며, ''n''개의 정점을 가진 경로 그래프에서 극대 독립 집합의 개수는 파도반 수열로 주어진다.^[6]^[31] 이 두 수열은 모두 플라스틱 수 1.324718...의 거듭제곱에 비례한다.

4. 알고리즘

컴퓨터 과학에서 독립 집합과 관련된 여러 계산 문제가 연구되었다.^[9]

최대 독립 집합 문제: 무방향 그래프에서 최대 독립 집합을 찾는 문제이다. 최대 독립 집합이 여러 개 있는 경우 하나만 출력하면 된다. "정점 패킹"이라고도 불린다.
최대 가중 독립 집합 문제: 정점에 가중치가 있는 무방향 그래프에서 최대 총 가중치를 갖는 독립 집합을 찾는 문제이다. 최대 독립 집합 문제는 모든 가중치가 1인 특수한 경우이다.
극대 독립 집합 나열 문제: 무방향 그래프에서 모든 극대 독립 집합의 목록을 출력한다. 최대 독립 집합은 모든 극대 독립 집합에 포함되어야 하므로, 극대 독립 집합 나열 문제 알고리즘을 서브루틴으로 사용하여 최대 독립 집합 문제를 해결할 수 있다.
독립 집합 결정 문제: 무방향 그래프와 숫자 ''k''가 주어졌을 때, 그래프에 크기가 ''k''인 독립 집합이 있는지 부울 값으로 출력한다.

처음 세 가지 문제는 실제 응용 분야에서 중요하며, 독립 집합 결정 문제는 NP-완전성 이론을 독립 집합 관련 문제에 적용하기 위해 필요하다.^[9]

다른 독립 집합의 부분 집합이 아닌 독립 집합을 "극대(maximal)"라고 하며, 이러한 집합은 지배 집합이기도 하다. 그래프는 최대 3^''n''/3개의 극대 독립 집합을 가질 수 있지만, 많은 그래프의 극대 독립 집합의 개수는 그보다 적다.

''n''-정점 사이클 그래프에서 극대 독립 집합의 개수는 페린 수열로 주어지며, ''n''-정점 경로에서 극대 독립 집합의 개수는 파도반 수열로 주어진다.^[31] 따라서, 둘 다 플라스틱 수 1.324718의 거듭제곱에 비례한다. NP-난해 문제를 다루는 알고리즘에서는 극대 독립 집합을 나열하는 처리를 서브루틴으로 사용하는 경우가 많다.

4. 1. 최대 독립 집합 문제

최대 독립 집합 문제(maximum independent set problem^영어)는 주어진 그래프에서 최대 독립 집합을 찾는 문제이다.^[9] 이 문제는 NP-난해 최적화 문제이며, "정점 패킹"이라고도 불린다.^[9]

최대 독립 집합 문제는 모든 정점 부분 집합을 검사하여 독립 집합인지 확인하는 무차별 대입 알고리즘(O(''n''² 2^''n''))보다 효율적으로 해결할 수 있다. 2017년 기준으로 다항식 공간을 사용하여 O(1.1996^''n'') 시간에 해결할 수 있으며,^[9] 최대 차수가 3인 그래프로 제한하면 O(1.0836^''n'') 시간에 해결할 수 있다.^[10]

4. 2. 극대 독립 집합 문제

주어진 그래프에서 극대 독립 집합을 찾는 문제이다.^[22] 이 문제는 다항 시간에 간단한 탐욕 알고리즘으로 풀 수 있다.^[22]

4. 3. 극대 독립 집합 나열 문제

주어진 그래프의 모든 극대 독립 집합을 찾는 문제이다. NP-난해 문제를 다룰 때 부분 단계로 자주 등장한다. 모든 극대 독립 집합을 O(3^n/3) 시간에 찾을 수 있는 알고리즘이 존재한다.^[22]

4. 4. 독립 집합 결정 문제

독립 집합 결정 문제는 주어진 그래프

G

가 주어진 크기

k

의 독립 집합을 포함하는지를 판정하는 결정 문제이다.^[7] 이는 그 여 그래프의 클리크 문제와 동치이며, NP-완전 문제이다.

독립 집합 결정 문제에서 입력은 무방향 그래프와 숫자 ''k''이며, 출력은 부울 값이다. 그래프에 크기가 ''k''인 독립 집합이 있으면 true이고, 그렇지 않으면 false이다.^[7]

독립 집합 문제는 클리크 문제와 상호 보완적이다. 그래프 ''G''의 클리크는 ''G''의 여 그래프의 독립 집합과 같으며, 그 반대도 성립한다. 따라서 클리크 문제와 관련된 결과에 따라, 독립 집합 결정 문제는 NP-완전이며, 이를 해결하는 효율적인 알고리즘이 존재하지 않는 것으로 여겨진다.^[7]

4. 5. 근사 알고리즘

컴퓨터 과학에서 최대 독립 집합 문제는 P=NP가 아닌 이상 다항 시간 내에 상수 인자로 근사될 수 없다.^[16] 이는 다항식 인자로 근사될 수 있는 문제만큼 어렵다는 것을 의미한다. 그러나 특정 종류의 그래프에서는 효율적인 근사 알고리즘이 존재한다.

평면 그래프에서는 다항 시간 내에 임의의 근사 비율 ''c'' < 1 까지 근사할 수 있다. 비슷한 다항 시간 근사 알고리즘은 마이너를 취하는 것에 닫혀 있는 모든 그래프족에서 존재한다.^[17]
유계 차수 그래프에서는 최대 차수의 고정된 값에 대해 상수 근사 비율을 갖는 효율적인 근사 알고리즘이 알려져 있다. 예를 들어, 각 단계에서 최소 차수 정점을 선택하고 이웃을 제거하는 탐욕 알고리즘은 최대 차수 Δ의 그래프에서 (Δ+2)/3의 근사 비율을 달성한다.^[18] 3-정규 3-에지-채색 가능 그래프에 대한 최대 독립 집합 문제조차도 APX-완전이다.^[19]
구간 그래프에서 독립 집합은 겹치지 않는 구간의 집합을 의미하며, 최초 마감 기한 우선 스케줄링을 사용하면 다항 시간 내에 최대 독립 집합을 정확하게 찾을 수 있다.
기하학적 교차 그래프에서 독립 집합은 분리된(겹치지 않는) 도형의 집합을 의미한다. 최대 독립 집합을 찾는 문제는 여전히 NP-완전이지만, 일반적인 최대 독립 집합 문제보다 근사하기 쉽다.
''d''-클로-프리 그래프에서 최대 독립 집합에 대한 (''d''-1)-근사 알고리즘을 얻을 수 있다.

4. 6. 특정 그래프에서의 알고리즘

많은 종류의 그래프에서 최대 가중치 독립 집합은 다항 시간 안에 찾을 수 있다. 유명한 예로는 클로가 없는 그래프^[11], P₅-프리 그래프^[12] 및 완전 그래프가 있다.^[13] 현 그래프의 경우, 최대 가중치 독립 집합은 선형 시간 안에 찾을 수 있다.^[14]

모듈 분해는 최대 가중치 독립 집합 문제를 해결하는 데 좋은 도구이며, 코그래프에 대한 선형 시간 알고리즘이 그 기본적인 예이다.

쾨니그의 정리 (그래프 이론)에 따르면, 이분 그래프에서 최대 독립 집합은 이분 매칭 알고리즘을 사용하여 다항 시간 안에 찾을 수 있다.

5. 독립 집합의 개수 계산

계산 문제 #IS는 무방향 그래프가 주어졌을 때, 그래프에 독립 집합이 몇 개 있는지 묻는 문제이다. 이 문제는 풀기 어려운데, 최대 차수가 3인 그래프에서도 ♯P-완전이다.^[23] NP가 RP와 다르다고 가정하면, 최대 차수가 6인 그래프에서는 무작위화를 사용한 완전 다항 시간 근사 계획 (FPRAS)을 갖는다는 의미에서 이 문제에 대한 실용적인 근사 알고리즘을 사용할 수 없다.^[24] 그러나 최대 차수가 5인 경우에는 완전 다항 시간 근사 계획 (FPTAS)이 존재한다.^[25] 이분 그래프에서의 독립 집합 계산 문제인 #BIS 또한 최대 차수가 3인 그래프에서도 ♯P-완전이다.^[26]

#BIS가 FPRAS를 허용하는지는 알려져 있지 않다.^[27]

6. 응용

구간 그래프에서 최대 독립 집합을 찾는 문제는 작업 스케줄링 문제 해결에 응용될 수 있다. 컴퓨터에서 실행해야 하는 작업 집합이 주어졌을 때, 서로 간섭 없이 실행할 수 있는 최대 작업 집합을 찾는 것이다. 이 문제는 최초 마감 기한 우선 스케줄링을 사용하여 다항 시간 내에 정확하게 해결할 수 있다.^[28]

기하학적 교차 그래프에서 최대 독립 집합을 찾는 문제는 자동 라벨 배치에 응용될 수 있다. 지도에서 일련의 위치가 주어지면, 이러한 위치 근처에서 분리된 직사각형 라벨의 최대 집합을 찾는 것이다.

최대 독립 집합과 그 여집합인 최소 정점 덮개 문제는 많은 이론적 문제의 계산 복잡도를 증명하는 데 사용된다.^[28] 또한, 최대 독립 집합은 유전적 구성 요소를 발견하여 합성 유전 시스템을 설계하는 데 유용한 모델로 사용된다.^[29]

참조

_[1] harvtxt
_[2] harvtxt
_[3] 간행물 "Strong" NP-Completeness Results: Motivation, Examples, and Implications 1978-07-01
_[4] 문서
_[5] harvtxt
_[6] harvtxt
_[7] harvtxt
_[8] harvtxt
_[9] harvtxt
_[10] harvtxt
_[11] harvtxt
_[11] harvtxt
_[11] harvtxt
_[11] harvtxt
_[11] harvtxt
_[12] harvtxt
_[13] harvtxt
_[14] harvtxt
_[15] harvtxt
_[16] 간행물 Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness https://basepub.daup[...] 2005
_[17] harvtxt
_[17] harvtxt
_[18] harvtxt
_[19] 서적 Proceedings of the 5th International Conference on Algorithms and Complexity 2003
_[20] Citation An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs 2021-06-07
_[21] 서적 2013 IEEE 54th Annual Symposium on Foundations of Computer Science 2013-10
_[22] harvtxt
_[23] 간행물 On Markov Chains for Independent Sets https://www.scienced[...] 2000-04-01
_[24] 서적 2010 IEEE 51st Annual Symposium on Foundations of Computer Science 2010
_[25] 간행물 Approximation via Correlation Decay When Strong Spatial Mixing Fails https://epubs.siam.o[...] 2019
_[26] 간행물 Computational complexity of counting problems on 3-regular planar graphs https://www.scienced[...] 2007-09-24
_[26] 간행물 A Fixed-Parameter Perspective on #BIS 2019-10-01
_[27] 서적 Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms https://epubs.siam.o[...] Society for Industrial and Applied Mathematics 2020
_[28] 서적 The algorithm design manual Springer 2012
_[29] 간행물 Automated design of thousands of nonrepetitive parts for engineering stable genetic systems https://www.nature.c[...] 2020-07-13
_[30] 서적 Algebraic Graph Theory Springer
_[31] 간행물 The number of maximal independent sets in connected graphs
_[32] 서적

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com