Day 062-Q1 — オイラー標数・Genus計算（埋め込みグラフ / 回転システム）

問題

$N$ 頂点 $M$ 辺の単純連結無向グラフ $G$ が与えられる。各頂点の回転システム（rotation system: 時計回りの隣接辺順序）が入力として与えられる。

以下を計算して出力せよ：

• 面の数 $F$（回転システムから算出）
• オイラー標数 $\chi = V - E + F$
• 埋め込みの種数（Genus）$g$（$\chi = 2 - 2g$ より）

入出力例

4 6
1 2
1 3
1 4
2 3
2 4
3 4
1: 2 3 4
2: 1 4 3
3: 1 2 4
4: 1 3 2

V=4 E=6 F=4 chi=2 g=0

$K_4$（完全グラフ4頂点）の平面埋め込み。オイラー標数 $\chi=2$、種数 $g=0$ → 平面グラフ。

概念図: Dart・回転システム・面の列挙

ヒント（段階的開示）

next_dart = {}
for v in range(1, N+1):
    rot = rotation[v]
    for i, u in enumerate(rot):
        w = rot[(i+1) % len(rot)]
        next_dart[(u, v)] = (v, w)

visited = set(); F = 0
for start in next_dart:
    if start not in visited:
        F += 1
        d = start
        while d not in visited:
            visited.add(d); d = next_dart[d]

chi = N - M + F; g = (2 - chi) // 2

模範解答 (Python)

コピーimport sys
from collections import defaultdict
input = sys.stdin.readline

def main():
    line = input().split()
    N, M = int(line[0]), int(line[1])
    edges = []
    for _ in range(M):
        u, v = map(int, input().split())
        edges.append((u, v))

    rotation = defaultdict(list)
    for _ in range(N):
        line = input().split(':')
        v = int(line[0].strip())
        neighbors = list(map(int, line[1].split()))
        rotation[v] = neighbors

    twin = {}
    next_dart = {}
    for u, v in edges:
        twin[(u, v)] = (v, u)
        twin[(v, u)] = (u, v)

    for v in range(1, N + 1):
        rot = rotation[v]
        d = len(rot)
        for i, u in enumerate(rot):
            w = rot[(i + 1) % d]
            next_dart[(u, v)] = (v, w)

    all_darts = set(next_dart.keys())
    visited = set()
    F = 0
    for start in all_darts:
        if start not in visited:
            F += 1
            d = start
            while d not in visited:
                visited.add(d)
                d = next_dart[d]

    chi = N - M + F
    g = (2 - chi) // 2
    print(f"V={N} E={M} F={F} chi={chi} g={g}")

main()

Step-by-Step 解説

Step 1: dart の定義と回転システム

各無向辺 $(u,v)$ を $dart(u,v)$ と $dart(v,u)$ に分割（計 $2M$ 本）。頂点 $v$ の回転システム（隣接頂点の時計回り順）から $\text{next\_dart}[(u,v)] = (v,w)$ を定義する（$w$ は $v$ の回転リストで $u$ の次の頂点）。

Step 2: 面の列挙

未訪問 dart からサイクルを辿る。各サイクルが1面に対応。計算量 $O(M)$。全 $2M$ dart を exactly 1 回ずつ訪問するため、面の総計は正確に $F$ となる。

Step 3: Euler 標数と種数

$\chi = V - E + F$。連結グラフでは $\chi = 2 - 2g$（$g$ は向き付け可能曲面の種数）。平面グラフ（$g=0$）では $\chi=2$（球面）、トーラス（$g=1$）では $\chi=0$。

よくあるミス

次のステップ

• 発展問題: 非平面グラフ（$K_5$, $K_{3,3}$）の最小 genus 計算（NP困難・近似法）
• 関連: Kuratowski定理・平面グラフ双対・四色定理の計算機証明

自己評価