Day 019-Q5 | 平面グラフの双対・最小カット

問題

平面グラフ（辺が交差しない埋め込みを持つグラフ）$G$ が与えられる。Q1: 双対グラフ $G^*$ を構築せよ。Q2: 2頂点 $s, t$ 間の 最小 s-t カット を求めよ（$s, t$ は外面上に隣接）。

ヒント: 平面グラフの最小 s-t カットは、双対グラフ上の最短経路に等価。

制約

$2 \le N \le 10^5$

$N-1 \le M \le 3N-6$

辺の重み $w_e \ge 1$

入出力例

入力例 1

出力例 1

ヒント (段階的開示)

ヒント1: 方向性

平面グラフには双対グラフが存在する。$G$ の各面が $G^*$ の頂点、$G$ の各辺が $G^*$ の辺。

ヒント2: アプローチ

最小カット = 双対グラフ上の最短経路。$G$ で $s$-$t$ を分離するカットは $G^*$ での経路に対応。よって最小カット = 最短経路（ダイクストラ）。

ヒント3: 誘導

# DCEL: 各辺に2つの有向辺、各有向辺に rev と next
# 面の列挙: face[e] が未割当なら、next[rev[e]] で同じ面を辿る
# 双対辺: face[2*i] と face[2*i+1] を繋ぐ

模範解答 (Python)

import sys
from collections import defaultdict
import heapq
input = sys.stdin.readline

def solve():
    N, M = map(int, input().split())
    s, t = map(int, input().split())
    s -= 1; t -= 1

    edges = []
    adj = defaultdict(list)
    for i in range(M):
        u, v, w = map(int, input().split())
        u -= 1; v -= 1
        adj[u].append((v, 2 * i))
        adj[v].append((u, 2 * i + 1))
        edges.append((u, v, w))

    rev = [None] * (2 * M)
    for i in range(M):
        rev[2 * i] = 2 * i + 1
        rev[2 * i + 1] = 2 * i

    weight = [0] * (2 * M)
    for i, (u, v, w) in enumerate(edges):
        weight[2 * i] = w
        weight[2 * i + 1] = w

    # 簡略: 入力が DCEL 形式で next_edge を直接構築できると仮定
    next_edge = list(range(2 * M))

    face_of = [-1] * (2 * M)
    face_cnt = 0
    for start in range(2 * M):
        if face_of[start] != -1: continue
        e = start
        while face_of[e] == -1:
            face_of[e] = face_cnt
            e = next_edge[rev[e]]
        face_cnt += 1

    dual_adj = defaultdict(list)
    for i in range(M):
        f1 = face_of[2 * i]
        f2 = face_of[2 * i + 1]
        if f1 != f2:
            w = weight[2 * i]
            dual_adj[f1].append((f2, w))
            dual_adj[f2].append((f1, w))

    f_s = f_t = -1
    for i, (u, v, w) in enumerate(edges):
        if (u == s and v == t) or (u == t and v == s):
            f_s = face_of[2 * i]
            f_t = face_of[2 * i + 1]
            break

    if f_s == -1:
        print("s と t は直接隣接していない")
        return

    INF = float('inf')
    dist = [INF] * face_cnt
    dist[f_s] = 0
    heap = [(0, f_s)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in dual_adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    print(f"最小 s-t カット = {dist[f_t]}")

solve()

Step-by-Step 解説

1平面グラフ
辺が交差しない平面埋め込みを持つ。Euler の公式: $V - E + F = 2$。

2DCEL
各辺は2つの有向辺（half-edge）を持つ。各 half-edge は rev（逆方向）と next（同じ面を反時計回り）。

3面の列挙
next[rev[e]] を繰り返すと一つの面を構成する全 half-edge を列挙。$O(M)$。

4双対グラフの構築
各辺の両側の面を見つけて双対辺を作る。$O(M)$。

5最小カットの計算
$s, t$ が隣接する辺 $e^*$ を持つ場合、双対グラフを $e^*$ で切断した2つの面を起点・終点としてダイクストラ。

よくあるミス

ミス	原因	正しい書き方
next ポインタの方向	時計回り/反時計回りの混乱	half-edge の left face を一貫定義
外面の特定	「最大の面」が外面とは限らない	座標を使い最大面積を外面とする
s-t が直接隣接しない	双対の対応面を間違える	仮想辺を追加して隣接させる

次のステップ

発展: 平面グラフの最小全域木、平面グラフの彩色（4色定理）

自己評価

完全理解おおむね理解要復習

Day 019-Q5 — 双対グラフ・平面グラフ

問題

制約