그래프에 포함된 정점 $0$개 이상을 포함한 집합이 다음 조건을 만족할 경우 그 집합을 그래프의 독립 집합(Independent Set)이라고 한다.1
- 그래프에 존재하는 임의의 간선이 정점 $u$와 정점 $v$를 연결할 때, $u$와 $v$ 중 최소한 한 정점은 집합에 속하지 않는다.
간단히 말하면 독립 집합에 속한 정점들 사이를 직접 연결하는 간선이 없다는 것이다. 이것은 트리에도 똑같이 적용할 수 있고, 트리에 존재하는 독립 집합을 트리의 독립 집합이라고 한다. 또한 독립 집합들 중 가장 많은 정점을 포함하는 집합을 최대 독립 집합(Maximal Independent Set)이라고 한다. 하나의 그래프/트리에 두 개 이상의 최대 독립 집합이 존재할 수도 있다.
독립 집합을 정의할 때의 특이사항은 그래프에 고리가 존재할 때 생기는데, 위에 나온 정의대로라면 고리가 달린 정점은 어떤 독립 집합에도 포함되지 않게 된다. 따라서 서로 다른 정점들 사이에 간선이 존재하지 않아도 독립 집합에 정점을 포함시킬 수 없는 경우가 생길 수 있다. [이것이 맞는 정의인지 찾아봤으나 독립 집합 자체가 보통 단순 그래프에서 정의되기 때문에 이런 경우에 대한 언급이 있는 문서를 찾지 못했다. 그래서 정의가 잘 됐는지는 판별하지 못했지만, 고리 역시 엄연한 간선이므로 맞는 정의라고 간주해도 괜찮다.]
일반적으로 독립 집합을 다룰 경우 대부분 최대 독립 집합을 다루게 된다. 일반적인 그래프의 최대 독립 집합을 구하는 문제는 NP-Hard이기 때문에 잘 다루지 않으며 대부분 트리의 최대 독립 집합을 다루게 될 것이다. (이분 그래프같이 최대 독립 집합을 다항 시간에 구할 수 있는 그래프도 존재하지만 논외로 한다.) 트리의 최대 독립 집합을 구하는 문제는 DP로 풀 수 있으며, 트리 DP 글에 간단하게 설명이 되어 있으므로 여기서는 설명을 생략한다.
그래프에 포함된 정점 $0$개 이상을 포함한 집합이 다음 조건을 만족할 경우 그 집합을 그래프의 클리크(Clique)라고 한다.
- 집합에 존재하는 임의의 서로 다른 두 정점 사이에 항상 간선이 존재한다.
간단히 말하면 그래프의 부분 그래프 중 완전 그래프인 것에서 정점들만 포함한 집합이라고 할 수 있다. 이 정의에는 고리나 다중 간선이 문제가 되는 부분이 없다.
만약 클리크에 어떤 정점을 추가하더라고 클리크가 되지 않을 경우 그 클리크를 최대 클리크(Maximal Clique)라고 한다. 일반적인 그래프에서 최대 클리크를 구하는 문제는 최대 독립 집합을 구하는 문제와 마찬가지로 NP-Hard이다. 구하는 것을 변형해서 다항 시간에 풀 수 있는 문제를 만들 수 있긴 하지만 이런 식의 변형 문제는 거의 나오지 않는다.
[참고 링크]
- 다른 영어 표현으로 Stable Set, Coclique, Anticlique가 존재하지만 잘 쓰이지 않는다. [본문으로]
'Algorithm > H. Trees & Graphs' 카테고리의 다른 글
| 123. Topological Sorting (0) | 2022.04.30 |
|---|---|
| 122. Directed Acyclic Graph (0) | 2022.04.29 |
| 120. Dial's Algorithm (0) | 2022.03.09 |
| 119. 0-1 BFS (0) | 2022.03.07 |
| 118. Shortest Path Faster Algorithm (0) | 2022.03.07 |
