독립 집합(그래프 이론)

그래프 이론에서, 독립 집합, 안정 집합, coclique 또는 반 기울기는 그래프의 꼭지점 집합이며, 그 중 두 개가 인접하지 않습니다.즉, S$\displaystyle$S의 $두{\displaystyle }$ 정점에 대해 두 정점을 연결하는 가장자리가 없도록 S$\displaystyle$S의 $집합$입니다.마찬가지로 그래프의 각 엣지에는$$S\$displaystyle$ S$\backslash$에 최대 1개의 엔드포인트가 있습니다.이 세트는 그래프 보완에 포함된 클리크일 경우에만 독립적입니다.독립 집합의 크기는 해당 집합이 포함하는 정점의 수입니다.독립 집합은 "내부 안정 집합"이라고도 불리며, "안정 집합"은 단축입니다.^[1]

최대 독립 집합은 다른 독립 집합의 적절한 하위 집합이 아닌 독립 집합입니다.

최대 독립 집합은 주어진 $그래프{\displaystyle }$ G$(\displaystyle$ G$)$에 대해 가능한 가장 큰 크기의 독립 집합입니다. 이 크기는$$G(\$displaystyle$ G$)$의 $독립{\displaystyle }$ 번호라고 하며 일반적으로${\displaystyle }$α($)\displaystyle \alpha$^[2]$G)$로 표시됩니다.이러한 집합을 찾는 최적화 문제를 최대 독립 집합 문제라고 합니다.이것은 강한 NP-하드 문제입니다.^[3]따라서 그래프의 최대 독립 집합을 찾는 효율적인 알고리즘은 존재하지 않을 수 있습니다.

모든 최대 독립 집합도 최대이지만, 역의 의미는 반드시 유지되지는 않습니다.

특성.

커버/패킹 문제 쌍
문제 해결 포장 문제 최소 세트 커버 최대 세트 패킹 최소 가장자리 커버 최대 일치 최소 정점 커버 최대 독립 집합 휴지통 덮개 휴지통 패킹 폴리곤 피복 직사각형 패킹
v t

다른 그래프 매개 변수와의 관계

집합은 그래프 보완의 한 집단인 경우에만 독립적이므로 두 개념은 상호 보완적입니다.사실, 큰 클리프가 없는 충분히 큰 그래프는 램지 이론에서 탐구된 주제인 큰 독립 집합을 가지고 있다.

집합은 보체가 ^[4]정점 커버인 경우에만 독립적입니다.따라서 가장 큰 독립 $(\displaystyle \alpha(G))$와 최소 정점 $(\displaystyle \beta(G))$ 크기의$$ 합계는 그래프 내의 정점 수와 같다.

$그래프 G의$정점 색상은 정점 세트를 독립된 서브셋으로 분할하는 것에 대응합니다$$.따라서 정점 색칠에 필요한 최소 색수인 색수${\displaystyle }\delta {\displaystyle }$($)\displaystyle\chi$$G)$는 적어도$$G(\$displaystyle$ G$)$의 $정점수$와$($G)의 몫은 G(\$displaystyle \alpha(G$

고립된 정점이 없는 초당 그래프에서, 최대 독립 집합의 정점 수는 최소 에지 커버의 에지 수와 같습니다. 이것이 쾨니그의 정리입니다.

최대 독립 집합

다른 독립 집합의 적절한 하위 집합이 아닌 독립 집합을 최대 집합이라고 합니다.이런 세트가 지배적이다.모든 그래프에는 최대^n/3 3개의 독립 ^[5]집합이 포함되어 있지만, 많은 그래프에는 훨씬 적은 수의 독립 집합이 포함되어 있습니다.n-vertex 주기 그래프의 최대 독립 집합 수는 Perrin 번호로 지정되며, n-vertex 경로 그래프의 최대 독립 집합 수는 Padovan ^[6]시퀀스로 지정된다.따라서 두 숫자는 플라스틱 번호인 1.324718의 거듭제곱에 비례합니다.

독립 세트 찾기

컴퓨터 과학에서, 독립적인 집합과 관련된 몇 가지 계산 문제가 연구되었다.

• 최대 독립 집합 문제에서 입력은 무방향 그래프이고 출력은 그래프에서 최대 독립 집합입니다.최대 독립 세트가 여러 개 있는 경우 하나만 출력하면 됩니다.이 문제를 "버텍스 패킹"이라고 부르기도 합니다.
• 최대 가중치 독립 집합 문제에서 입력은 정점에 가중치가 있는 무방향 그래프이고 출력은 최대 총 가중치를 갖는 독립 집합입니다.최대 독립 집합 문제는 모든 무게가 1인 특수한 경우입니다.
• 최대 독립 집합 나열 문제에서 입력은 무방향 그래프이며 출력은 모든 최대 독립 집합의 목록입니다.최대 독립 집합은 모든 최대 독립 집합 사이에 포함되어야 하기 때문에 최대 독립 집합 나열 문제에 대한 알고리즘을 서브루틴으로 사용하여 최대 독립 집합 문제를 해결할 수 있습니다.
• 독립 집합 결정 문제에서 입력은 무방향 그래프와 숫자 k이며 출력은 부울 값입니다. 그래프에 독립 집합이 k이면 true이고 그렇지 않으면 false입니다.

이러한 문제들 중 처음 세 가지는 모두 실제 적용에서 중요하다. 독립 집합 결정 문제는 독립 집합과 관련된 문제에 NP-완전성 이론을 적용하기 위해 필요하지만 독립 집합 결정 문제는 그렇지 않다.

최대 독립 세트 및 최대 CLI 수

독립 집합 문제와 clique 문제는 상호 보완적입니다.G 내의 clique는 G의 보완 그래프 내의 독립 집합이며, 그 반대도 마찬가지입니다.따라서 많은 계산 결과가 어느 문제에나 동일하게 적용될 수 있습니다.예를 들어 clique 문제와 관련된 결과에는 다음과 같은 결과가 있습니다.

• 독립 집합 결정 문제는 NP-완전이기 때문에 이를 해결하기 위한 효율적인 알고리즘은 존재하지 않습니다.
• 최대 독립 집합 문제는 NP-hard이며 또한 근사하기 어렵습니다.

임의 그래프에서 최대 클리어와 최대 독립 집합 간의 밀접한 관계에도 불구하고, 특수 클래스의 그래프로 제한되는 경우 독립 집합 및 클리크 문제는 매우 다를 수 있습니다.예를 들어, 희박한 그래프(그래프에 모서리의 번호는 가장 일정한 때의 vertices에 subgraph), 최대 클리크 그리고 정확하게 선형 때에[7] 하지만, 그래프의 같은 수업 또는 한정적 학위 그래프의 더 제한된 심지어 수업 시간을 최대 indepen을 찾고 찾을 수 있을 것 크기 경계가 되고 있다.드nt 세트는 MAXSNP-complete로, 일정한 c(정도에 따라 다름)에 대해 최적 ^[8]c 계수 내에 있는 대략적인 해법을 찾는 것이 NP-hard임을 의미합니다.

최대 독립 집합 찾기

정확한 알고리즘

최대 독립 집합 문제는 NP-hard입니다.그러나 모든 정점 서브셋을 검사하고 독립 집합인지 여부를 확인하는 순진한 무차별 포스 알고리즘에 의해 주어진 O(n²ⁿ 2) 시간보다 더 효율적으로 해결할 수 있습니다.

2017년 현재 다항식 ^[9]공간을 사용하여 O(1.196ⁿ) 시간 내에 풀 수 있다.최대 도수가 3인 그래프로 제한하면 시간 O(1.0836ⁿ)^[10] 내에 해결할 수 있습니다.

많은 그래프 클래스의 경우 다항식 시간에서 최대 가중치 독립 집합을 찾을 수 있습니다.유명한 예로는 발톱이 없는 그래프,^[11] P가₅ 없는^[12] 그래프, 완벽한 ^[13]그래프 등이 있습니다.화음 그래프의 경우 선형 ^[14]시간에서 최대 무게 독립 집합을 찾을 수 있습니다.

모듈 분해는 최대 무게 독립 집합 문제를 해결하기 위한 좋은 도구이며, 코그래프의 선형 시간 알고리즘이 이에 대한 기본적인 예입니다.또 다른 중요한 ^[15]도구는 Tarjan이 설명한 clike separator입니다.

쾨니그의 정리는 초당 그래프에서 초당 일치 알고리즘을 사용하여 다항 시간에 최대 독립 집합을 찾을 수 있다는 것을 암시한다.

근사 알고리즘

일반적으로 최대 독립 집합 문제는 (P = NP가 아닌 한) 다항식 시간의 상수 인자에 근사할 수 없습니다.실제로 Max Independent Set은 일반적으로 Poly-APX-complete이므로 다항식 ^[16]인수에 근사할 수 있는 문제만큼 어렵습니다.그러나 제한된 그래프 클래스에 대한 효율적인 근사 알고리즘이 있다.

평면 그래프에서, 최대 독립 집합은 다항 시간에서의 어떤 근사 비율 c < 1에 근사할 수 있다. 유사한 다항 시간 근사 체계는 ^[17]부차적 취하에 닫힌 모든 그래프 패밀리에 존재한다.

유계도 그래프에서 효과적인 근사 알고리즘은 최대도의 고정값에 대해 일정한 근사비로 알려져 있다. 예를 들어, 각 단계에서 그래프에서 최소도 정점을 선택하고 그 이웃을 제거함으로써 최대 독립 세트를 형성하는 탐욕 알고리즘은 근사 비율을 달성한다.o/(δ+2)/3(최대 차수 ^[18]δ의 그래프).그러한 예에 대한 근사 경도 한계는 Berman & Karpinski(1999년)에서 입증되었다.실제로 3-일반적인 3-엣지 컬러 그래프의 Max Independent Set도 APX ^[19]완전입니다.

구간 교차 그래프의 독립 집합

구간 그래프는 노드가 1차원 구간(예: 시간 간격)이며 교차하는 경우에만 두 구간 사이에 가장자리가 있는 그래프입니다.구간 그래프의 독립 집합은 겹치지 않는 간격 집합일 뿐입니다.인터벌 그래프에서 최대 독립 집합을 찾는 문제는 예를 들어 작업 스케줄링의 맥락에서 연구되어 왔습니다. 즉, 컴퓨터에서 실행해야 하는 작업 집합이 주어지면 서로 간섭하지 않고 실행할 수 있는 최대 작업 집합을 찾아야 합니다.이 문제는 가장 이른 기한의 첫 번째 일정을 사용하여 정확하게 다항식 시간에 해결할 수 있습니다.

기하학적 교차 그래프의 독립 집합

기하학적 교차 그래프는 노드가 기하학적 모양이고 교차하는 경우에만 두 모양 사이에 가장자리가 있는 그래프입니다.기하학적 교차 그래프에서 독립 집합은 서로 겹치지 않는(중첩되지 않는)예를 들어, 기하학적 교차 그래프에서 최대 독립 집합을 찾는 문제는 자동 레이블 배치의 맥락에서 연구되었습니다. 즉, 지도에서 위치 집합을 지정하면 이러한 위치 근처에서 최대 분리 직사각형 레이블 집합을 찾습니다.

교차로 그래프에서 최대 독립 집합을 찾는 것은 여전히 NP-완료이지만 일반적인 최대 독립 집합 문제보다 근사하기가 쉽습니다.최근 조사는 Chan & Har-Peled(2012)의 소개에서 확인할 수 있다.

최대 독립 집합 찾기

최대 독립 집합을 찾는 문제는 사소한 탐욕 ^[20]알고리즘에 의해 다항식 시간에 해결될 수 있다.모든 최대 독립 집합은 시간 O(3^n/3) = O(1.4423ⁿ)에서 찾을 수 있다.

적용들

최대 독립 집합과 그 보완인 최소 정점 커버 문제는 많은 이론적 ^[21]문제의 계산 복잡성을 증명하는 데 관여한다.이들은 또한 실제 최적화 문제에 유용한 모델 역할을 한다. 예를 들어 최대 독립 집합은 공학적 유전자 ^[22]시스템을 설계하기 위한 안정적인 유전자 구성 요소를 발견하는 데 유용한 모델이다.

「 」를 참조해 주세요.

• 독립 에지 집합은 공통 정점을 가지지 않는 에지 집합입니다.그것은 보통 매칭이라고 불린다.
• 정점 색상은 정점을 독립된 집합으로 분할한 것입니다.

메모들

레퍼런스

외부 링크

• Weisstein, Eric W. "Maximal Independent Vertex Set". MathWorld.
• 최대 클리크, 최대 독립 세트, 최소 정점 커버 및 정점 색상에 대한 도전적인 벤치마크
• 독립 집합과 정점 커버, 하난 아야드.