1. 독립 집합(Independent set)
어떤 그래프에서 서로 인접하지 않는 정점들의 집합을 그 그래프의 독립 집합(Independent set)이라고 합니다.
다시 말하면 독립 집합의 정점들은 해당 그래프에서 어떤 간선으로도 연결되어 있지 않습니다.
즉, 두 끝 모두에 독립 집합의 정점이 위치하는 간선은 존재하지 않습니다.
그렇다면 간선을 두 종류로 나눌 수 있는데, 하나는 한 쪽 끝만 독립 집합의 정점인 간선이고, 다른 하나는 두 끝 다 독립 집합의 정점이 아닌 간선으로 나눌 수 있습니다.
위 그림의 파란색 정점은 독립 집합을 나타내는데, 어떠한 간선도 두 파란색 점을 연결하지 않는 것을 볼 수 있습니다.
https://ko.wikipedia.org/wiki/독립집합
독립집합 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전.
ko.wikipedia.org
2. 극대 독립 집합(Maximal independent set)
다른 독립 집합의 부분 집합이 아닌 독립 집합을 극대 독립 집합(Maximal independent set)이라고 합니다.
더 큰 독립 집합에 포함되지 않으므로, 극대 독립 집합 외부에는 독립 집합을 유지하면서 결합할 수 있는 정점이 없습니다.
따라서 극대 독립 집합에 포함되지 않는 모든 정점을 살펴보면, 최소 하나 이상의 극대 독립 집합의 정점과 연결되어 있습니다.
위 그림은 정육면체 그래프의 극대 독립 집합을 나타낸 그림인데, 색칠되지 않은 모든 점은 색칠된 점과 연결되어 있습니다.
https://en.wikipedia.org/wiki/Maximal_independent_set
Maximal independent set - Wikipedia
From Wikipedia, the free encyclopedia Independent set which is not a subset of any other independent set The graph of the cube has six different independent sets (two of them are maximum), shown as the red vertices. In graph theory, a maximal independent s
en.wikipedia.org
3. 최대 독립 집합(Maximum independent set)
그래프의 독립 집합 중에서 정점의 개수가 가장 많은(최대 크기) 독립 집합을 최대 독립 집합(Maximum independent set)이라고 합니다.
최대 독립 집합은 극대 독립 집합에 포함되고, 극대 독립 집합 중에 크기가 최대인 독립 집합과 최대 독립 집합은 같습니다.
4. 꼭짓점 덮개(Vertex cover)
독립 집합의 개념과 반대로, 어떤 정점들과 연결된 간선이 그래프의 모든 간선일 경우 이 정점들의 집합을 꼭짓점 덮개(Vertex cover)라고 합니다.
(마치 아싸들은 독립 집합, 인싸들은 꼭짓점 덮개...)
위의 빨간색 점은 꼭짓점 덮개를 나타내고, 빨간색 선과 연결된 간선들은 모든 간선입니다.
위와 같이 꼭짓점 덮개 중 크기가 가장 작은 꼭짓점 덮개를 최소 꼭짓점 덮개(Minimum vertex cover)라고 합니다.
5. 독립 집합과 꼭짓점 덮개의 관계
독립 집합은 다른 어떤 정점과도 연결되지 않았으므로, 독립 집합에 포함되지 않는 정점들은 모든 정점들과 연결되어 있습니다.
따라서 어떤 그래프에서 독립 집합의 여집합은 꼭짓점 덮개이고, 최대 독립 집합의 여집합은 최소 꼭짓점 덮개가 됩니다.
(세상에 모든 인싸들을 제거하면 아싸들만 남는...?)
6. 쾨닉의 정리
독립 집합이 인접하지 않는 정점의 집합이라면, 인접하지 않는 간선들의 집합을 부합(Matching)이라고 합니다.
https://ko.wikipedia.org/wiki/부합_(그래프_이론)
부합 (그래프 이론) - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 최대 부합이 아닌 극대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다. 최대 부합의 예. 부합에 포함된 변들을 붉은 색으로 굵게 표시하였다.
ko.wikipedia.org
쾨닉의 정리에 따르면 이분 그래프에서 최대 부합(Maximum matching)의 크기는 최소 꼭짓점 덮개(Minimum vertex cover)의 크기와 같습니다.
따라서 최대 독립 집합의 크기는 전체 정점의 개수에서 최대 부합의 크기를 뺀 것과도 같습니다.
https://ko.wikipedia.org/wiki/쾨니그의_정리
쾨니그의 정리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전.
ko.wikipedia.org
7. 트리의 최대 독립 집합
그래프에서 최대 독립 집합을 찾는 문제는 NP-hard 문제에 해당되는 어려운 문제라고 합니다.
하지만 주어진 그래프가 트리 구조이면 그리디와 DP로 풀 수 있습니다.
1) 부모와 자식 관계에서 생각하기
부모와 자식은 인접하기 때문에 독립 집합이 되기 위해서는 두 가지 경우 중 하나입니다.
첫째, 부모가 포함되면 모든 자식은 포함될 수 없습니다.
둘째, 부모가 포함되지 않으면 모든 자식들은 포함되도 되고, 포함되지 않아도 됩니다.
그렇다면 최대 독립 집합은 두 경우 중 크기가 더 큰 경우입니다.
2) 리프 노드에서부터 생각하기
리프 노드는 자식 노드가 없습니다.
따라서 리프노드는 포함되거나 포함되지 않을 수 있습니다.
3) 루트 노드까지 재귀적으로 생각하기
어떤 노드를 루트로 하는 서브 트리의 최대 독립 집합의 크기는,
첫째, 자신을 포함하면서, 자식 노드를 루트로 하는 서브 트리에서 자식 노드를 포함하지 않는 최대 독립 집합의 크기의 합
둘째, 자신을 포함하지 않으면서, 자식 노드를 루트로 하는 서브 트리에서 최대 독립 집합의 크기의 합(자식 노드를 포함해도 되고, 안 해도 됨.)
이 두 가지 중에 최대값입니다.
리프 노드에서 점차 루트 노드까지 확장시켜 나가면 서브 트리가 점점 커져 전체 트리가 됩니다.
