고모리-후 트리

모든 쌍 최소 컷을 N-1번의 플로우로.

루비 II

선수 지식: 네트워크 플로우

1강 고모리-후 트리: 모든 쌍 최소 컷 공식

문제

무방향 가중 그래프에서, 모든 정점 쌍 $$(s, t)$$ 의 최소 $$s$$ – $$t$$ 컷(= 최대 흐름) 값을 알고 싶다. 쌍이 $\binom{n}{2}$ 개이니 각각 max-flow를 돌리면 $$O(n^2)$$ 번. 고모리–후 트리(Gomory–Hu tree) 는 단 $$n-1$$ 번의 max-flow로 모든 쌍의 최소 컷을 담는 트리를 만든다.

정의

고모리–후 트리는 원래 정점들 위의 가중 트리 $$T$$ 로, 다음을 만족한다.

임의의 $$s, t$$ 에 대해, $$T$$ 의 $$s$$ – $$t$$ 경로 위 최소 가중치 간선 의 값이 원래 그래프의 최소 $$s$$ – $$t$$ 컷 값과 같다. 또 그 간선을 제거해 생기는 트리의 두 부분이 실제 최소 컷의 한 분할을 준다.

즉 트리 경로의 병목 간선이 곧 최소 컷. 모든 쌍 정보를 $$n-1$$ 개 숫자로 압축한 것이다.

왜 가능한가: 최소 컷의 비교차성

핵심은 무방향 그래프 최소 컷의 부분모듈/비교차(submodular, uncrossing) 성질이다. 두 최소 컷이 "교차"하면, 더 작거나 같은 두 개의 비교차 컷으로 바꿀 수 있다(uncrossing lemma). 따라서 모든 쌍 최소 컷이 라미나(laminar)·트리 구조로 정리될 수 있다.

또 다음 삼각 부등식류가 성립한다:

$\lambda(s, t) \ge \min(\lambda(s, r),\ \lambda(r, t)).$

여기서 $\lambda$ 는 최소 컷 값. 이로부터 $$n$$ 개 정점의 모든 쌍 $\lambda$ 값이 사실상 $$n-1$$ 개의 "결정적" 값으로 결정된다는 점이 트리 표현의 근거다.

Gusfield의 간단한 버전

원조 Gomory–Hu는 정점 수축이 필요해 구현이 번거롭다. Gusfield의 변형 은 수축 없이 같은 트리를 만든다.

parent[i] = 0  (모든 i > 0 의 부모를 0으로 초기화)
for s = 1 .. n-1:
    t = parent[s]
    f = maxflow(s, t)               # 원래 그래프에서
    weight[s] = f
    (S, V\S) = min-cut의 s쪽 집합
    for i = s+1 .. n-1:
        if i in S and parent[i] == t:
            parent[i] = s           # 부모 재배선
    if parent[t] in S:              # Gusfield 보정
        parent[s] = parent[t]; parent[t] = s; weight[s] = weight[t]; weight[t] = f

각 반복에서 max-flow를 한 번씩, 총 $$n-1$$ 번. min-cut의 한쪽 집합은 잔여 그래프에서 $$s$$ 로부터 도달 가능한 정점들.

결과 트리의 사용

$\lambda(u, v)$ = $$T$$ 에서 $$u$$ – $$v$$ 경로의 최소 간선 가중치. DFS/희소 테이블로 경로 최솟값을 $O(\log n)$ 또는 $$O(1)$$ 에 질의.

복잡도

$$n-1$$ 번의 max-flow. 일반 그래프 max-flow가 $$O(F)$$ 면 전체 $$O(nF)$$ . 모든 쌍을 따로 푸는 $O(n^2\ F)$ 대비 $$n$$ 배 빠르다.

다음 강의에서 Gusfield 변형의 완전한 구현을 본다.

2강 Gusfield 알고리즘 구현 공식

max-flow 백엔드

Dinic 또는 ISAP을 사용한다. 무방향 간선은 양방향 용량으로 모델링(각 방향 cap $$c$$ , 또는 단일 간선의 잔여를 양쪽으로).

struct Dinic {
    struct E { int to; long long cap; int rev; };
    vector<vector<E>> g; vector<int> level, it; int n;
    void init(int n_){ n=n_; g.assign(n,{}); }
    void addEdge(int u,int v,long long c){      // 무방향: 양방향 c
        g[u].push_back({v,c,(int)g[v].size()});
        g[v].push_back({u,c,(int)g[u].size()-1});
    }
    bool bfs(int s,int t){
        level.assign(n,-1); queue<int>q; level[s]=0; q.push(s);
        while(!q.empty()){int u=q.front();q.pop();
            for(auto&e:g[u]) if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[u]+1; q.push(e.to);} }
        return level[t]>=0;
    }
    long long dfs(int u,int t,long long f){
        if(u==t) return f;
        for(int&i=it[u]; i<(int)g[u].size(); i++){
            E&e=g[u][i];
            if(e.cap>0&&level[e.to]==level[u]+1){
                long long d=dfs(e.to,t,min(f,e.cap));
                if(d>0){e.cap-=d; g[e.to][e.rev].cap+=d; return d;} } }
        return 0;
    }
    long long maxflow(int s,int t){
        long long flow=0;
        while(bfs(s,t)){ it.assign(n,0); long long f;
            while((f=dfs(s,t,LLONG_MAX))>0) flow+=f; }
        return flow;
    }
};

매 max-flow 전에 그래프(잔여 용량)를 원상복구 해야 함에 유의(아래에서 재구축).

min-cut의 s쪽 집합

max-flow 후, 잔여 그래프에서 $$s$$ 로부터 BFS로 도달 가능한 정점이 컷의 $$s$$ 쪽.

vector<char> minCutSide(Dinic& d, int s){
    vector<char> vis(d.n, 0);
    queue<int> q; q.push(s); vis[s]=1;
    while(!q.empty()){int u=q.front();q.pop();
        for(auto&e:d.g[u]) if(e.cap>0 && !vis[e.to]){
            vis[e.to]=1; q.push(e.to);} }
    return vis;
}

Gusfield 본체

// edges: (u, v, w) 원본 무방향 간선들
vector<int> par;          // 트리 부모
vector<long long> wt;     // par 간선 가중치

void gomoryHu(int n, vector<tuple<int,int,long long>>& edges){
    par.assign(n,0); wt.assign(n,0);
    for(int s=1; s<n; s++){
        Dinic d; d.init(n);
        for(auto&[u,v,w]:edges) d.addEdge(u,v,w);   // 매번 새로 구축
        int t = par[s];
        wt[s] = d.maxflow(s,t);
        vector<char> side = minCutSide(d, s);
        for(int i=s+1; i<n; i++)
            if(side[i] && par[i]==t) par[i]=s;
        if(side[par[t]]){                            // Gusfield 보정
            par[s]=par[t]; par[t]=s;
            wt[s]=wt[t]; wt[t]=d.maxflow_cached_or_f(s,t,wt[s]);
        }
    }
}

실무에선 보정 줄에서 f(방금 구한 flow)를 변수로 들고 있다가 wt[t]=f로 둔다. 위 의사 호출은 그 값을 가리킨다.

경로 최솟값 질의

트리를 인접 리스트로 만든 뒤, $\lambda(u,v)$ = 경로 최소 간선. 작은 $$q$$ 면 LCA + 경로 분할, 큰 $$q$$ 면 희소 테이블(min) 또는 Kruskal 재구성 트리.

// par[]/wt[]로 트리 인접 리스트 구성 후
// dist 최솟값 LCA 또는 binary lifting으로 lambda(u,v) 질의

함정

매 반복마다 그래프 재구축(잔여 용량 오염 방지). 또는 용량 복원.
무방향 간선: 양방향 cap. 같은 쌍에 여러 간선이면 용량 합산.
$$n=1$$ 예외 처리. 비연결 그래프면 $\lambda=0$ 쌍 존재.

복잡도: $$n-1$$ 번의 Dinic. 작은 정수 용량/희소 그래프에서 수천 정점까지 실용적이다.