Chordal Graph
정의
Chordal Graph (현 그래프, Triangulated Graph) 는 모든 길이 4 이상의 사이클이 chord (사이클의 비인접 두 정점을 잇는 간선) 를 가지는 그래프. 즉 induced subgraph 로서 4-cycle 이상의 무현 (chord 없는) 사이클이 없음.
PS 에서는 NP-hard 문제 중 일부 (maximum clique, chromatic number, max independent set) 가 chordal 그래프에서는 다항 시간 으로 풀린다는 점이 핵심. 인식 (recognition) 자체도 다항.
문제 상황과 동기
일반 그래프에서 max-clique (최대 크기 완전 부분그래프), chromatic number (최소 색칠 수), max independent set (최대 독립집합) 은 모두 NP-hard. Naive backtracking 은 O(2^N). 근사조차 어렵다 (clique 는 근사 불가, chromatic 은 O(N^epsilon) 근사만 가능).
Chordal graph 에서는 세 문제 모두 O(V+E) greedy 로 최적해를 구할 수 있다. 핵심은 Perfect Elimination Ordering (PEO) 존재: 정점을 어떤 순서로 뽑으면 각 단계에서 현재 정점의 이웃들이 클리크 를 이룬다. 이 구조 덕에 greedy 가 최적.
실전 (ICPC, BOJ) 에서는 그래프가 chordal 임이 보장되거나, chordal 인지 판별해 분기 하는 문제. Interval graph (구간 그래프) 도 chordal 의 부분집합이라 동일 기법 적용.
핵심 성질
- Perfect Elimination Ordering (PEO) 존재. 정점을 어떤 순서로 정렬해 뽑으면 각 단계에서 현재 정점의 이웃들이 클리크 를 이룬다.
- chordal ↔ PEO 존재
- max clique, chromatic number, max independent set, min clique cover 모두 polynomial
- Interval Graph 는 chordal 의 부분집합
시각화
Maximum Cardinality Search (MCS)
PEO 를 구하는 표준 알고리즘. O(V + E).
Invariant: 매 단계마다 이미 뽑은 정점과 가장 많은 이웃을 공유하는 정점을 뽑는다. label[v] = 이미 뽑은 정점 중 v 의 이웃 수. 이 greedy 순서가 chordal 이면 PEO, 아니면 non-chordal.
MCS(G):
label[v] = 0 for all v
for i = n downto 1:
v = argmax(label[v] : v 아직 안 뽑힘)
order[i] = v
for each unselected neighbor u of v:
label[u] += 1
return order이 order 가 PEO 이면 (검증 O(V+E) 로 가능) 그래프는 chordal.
예시 추적 (4 정점, 간선 (1,2), (2,3), (3,4), (4,1), (1,3))
초기: label = [0, 0, 0, 0]
i=4: argmax -> 정점 1 (임의), label[2]++, label[4]++, label[3]++
order[4] = 1, label = [-, 1, 1, 1]
i=3: argmax -> 정점 3 (label 1), label[2]++, label[4]++
order[3] = 3, label = [-, 2, -, 2]
i=2: argmax -> 정점 2 또는 4 (label 2), 선택 2
order[2] = 2, label = [-, -, -, 2]
i=1: order[1] = 4
order = [4, 2, 3, 1] (역순으로 뽑았으므로 PEO 는 1-3-2-4)
검증: 1 의 후속 이웃 {3,2,4} 는 클리크? -> (3,2), (2,4), (4,3) 간선 필요
-> (1,3), (3,2), (2,4), (4,1) 간선만 있으면 (2,4) 간선 없음 -> non-chordal
-> 실제로는 (1,3) chord 가 있어 chordal구현 (C++)
// O(V + E). MCS (Maximum Cardinality Search) 로 PEO 계산 + 검증.
#include <bits/stdc++.h>
using namespace std;
int n; // 정점 수 (1-indexed)
vector<int> adj[1005]; // 인접 리스트
vector<int> mcs() {
vector<int> label(n+1, 0);
vector<bool> used(n+1, false);
vector<int> order(n+1); // order[1..n] = PEO 순서
for (int i = n; i >= 1; i--) {
int v = -1, max_label = -1;
for (int u = 1; u <= n; u++) {
if (!used[u] && label[u] > max_label) {
max_label = label[u];
v = u;
}
}
order[i] = v;
used[v] = true;
for (int u : adj[v]) {
if (!used[u]) label[u]++;
}
}
return order; // order[1] 부터 order[n] 까지가 PEO
}
bool verify_peo(vector<int>& order) {
// order[1..n] 이 PEO 인지 검증: 각 order[i] 의 후속 이웃들이 클리크?
map<int, int> pos; // pos[v] = v 의 order 상 위치
for (int i = 1; i <= n; i++) pos[order[i]] = i;
for (int i = 1; i <= n; i++) {
int v = order[i];
vector<int> later_neighbors; // v 보다 뒤에 오는 이웃들
for (int u : adj[v]) {
if (pos[u] > i) later_neighbors.push_back(u);
}
// later_neighbors 가 클리크인지 확인
set<pair<int,int>> edge_set;
for (int u : adj[v]) {
for (int w : adj[u]) {
if (u < w) edge_set.insert({u, w});
}
}
for (int a = 0; a < (int)later_neighbors.size(); a++) {
for (int b = a+1; b < (int)later_neighbors.size(); b++) {
int u = later_neighbors[a], w = later_neighbors[b];
if (u > w) swap(u, w);
if (edge_set.find({u, w}) == edge_set.end()) {
return false; // u-w 간선 없음 -> non-chordal
}
}
}
}
return true;
}
bool is_chordal() {
vector<int> order = mcs();
return verify_peo(order);
}검증 로직: PEO 의 각 정점 v 에 대해 v 보다 뒤에 오는 이웃들 이 모두 서로 인접해야 (클리크). 아니면 non-chordal.
구현 팁
- Priority Queue 로 최적화: label 최댓값 찾기를 O(log V) 로. 전체 O(E log V).
- 간선 집합: 검증 시
set<pair<int,int>>로 간선 존재 O(log E) 판정. - 1-indexed vs 0-indexed: BOJ 는 보통 1-indexed. 주의.
응용 (모두 O(V+E) 또는 O((V+E) log V))
Maximum Clique
PEO 따라 정점을 뽑으며 해당 정점 + 후속 이웃 의 크기를 max.
Minimum Coloring
PEO 의 역순으로 greedy coloring. 항상 최적.
Maximum Independent Set
PEO 의 정방향 greedy.
Minimum Clique Cover
위의 dual.
인식 (Recognition)
MCS 로 PEO 후보를 얻고 검증 O(V+E). 검증 실패하면 non-chordal.
복잡도
| 작업 | 비용 |
|---|---|
| Chordal 인식 | O(V + E) |
| Max Clique | O(V + E) |
| Chromatic | O(V + E) |
| Max Independent Set | O(V + E) |
함정
1. 일반 그래프에서 위의 알고리즘 사용 금지
PEO 가 없으면 greedy 가 최적이 아님. 반드시 chordal 인지 먼저 확인.
2. PEO 가 unique 가 아님
같은 chordal 그래프에 여러 PEO 가능. 어떤 PEO 를 쓰든 알고리즘 정답은 같음.
3. interval / split graph 와 혼동
interval graph 는 chordal 의 진부분집합. split graph 는 chordal + complement 도 chordal. 문제가 어떤 family 를 가정하는지 확인.
BOJ 연습 문제
| 번호 | 제목 | 링크 |
|---|---|---|
| BOJ 16003 | 자석 장난감 | kokoa-lab |
| BOJ 16365 | Square Root | kokoa-lab |
다른 출처 연습 문제
| 출처 | 제목 | 링크 |
|---|---|---|
| Library Checker | Chordal Graph Recognition | https://judge.yosupo.jp/problem/chordal_graph_recognition |
💬 댓글