Day 145-Q2 — Vizingの定理と辺彩色（Δ+1色によるバックトラック構成）

2026-09-06 赤色 Master / Phase 8+ ★★★★★★★★★ 辺彩色数は必ずΔまたはΔ+1色。単純貪欲の限界を実測する

問題

$N$ 頂点 $M$ 辺の単純無向グラフが与えられる。グラフの最大次数を $\Delta$ とする。

Vizingの定理により、このグラフの辺は必ず $\Delta+1$ 色以内で「隣接する辺（同じ頂点を共有する辺）が異なる色になるように」彩色できることが保証されている。

入力で与えられた辺の順序に従い、若い番号から順に「その辺の両端点に接続する既に彩色済みの辺が使っていない色のうち最小の色番号（$1$ から $\Delta+1$）」を貪欲に割り当てていく。 割り当て候補が全て使用済み（両端点で $\Delta+1$ 色全て使用中）になった辺が現れたら、その時点で使用されている最大の色番号を出力して終了せよ。全ての辺を彩色できた場合は、使用した最大の色番号（$\Delta$ または $\Delta+1$）を出力せよ。

（本問は「単純な貪欲法だとΔ+1色に収まらないことがある」ことを実際に確認し、真のVizingの定理の証明にはfan回転とKempe chain反転という非自明な操作が必要であることを体感するための問題）

入力形式

N M
u_1 v_1
:
u_M v_M

制約

$2 \le N \le 7$
$1 \le M \le 21$
単純グラフ（自己ループ・多重辺なし）
$1 \le u_i, v_i \le N$、$u_i \ne v_i$

入出力例

入力例1

3 3
1 2
2 3
1 3

出力例1

3

三角形$K_3$は各頂点次数2（$\Delta=2$）だが、3辺全てが互いに隣接するため3色必要（Class 2）。

概念図：K3の辺彩色（Class 2）

K3: Δ=2だが3色(Δ+1)が必要 1 2 3 色1 色2 色3 全辺が互いに隣接 → 3色全て相異なる必要あり

ヒント（段階的開示）

ヒント1（方向性）

辺彩色は「線グラフ（line graph）の頂点彩色」と等価。線グラフを陽に作らなくても、各頂点ごとに「その頂点に接続する辺が使用中の色集合」を管理すれば十分。

ヒント2（アプローチ）

単純な貪欲法（辺を1本ずつ処理し両端点で未使用の最小色を割り当てる）は、グラフによっては $\Delta+1$ 色を超えてしまうことがある。真のVizingの定理の構成的証明（Misra-Gries）では、色が衝突した際に「fan」と呼ばれる隣接辺の列を回転させたり、2色だけを使う交互路（Kempe chain）を反転させたりして必ず $\Delta+1$ 色以内に収める。本問ではその手前段階として単純貪欲がどこまで機能するかを実測する。

ヒント3（誘導） 
used_colors = [set() for _ in range(N + 1)]
max_color_used = 0
for (u, v) in edges:
    c = 1
    while c in used_colors[u] or c in used_colors[v]:
        c += 1
    if c > delta + 1:
        print(max_color_used)
        return
    used_colors[u].add(c)
    used_colors[v].add(c)
    max_color_used = max(max_color_used, c)
print(max_color_used)

色番号 $c$ を $1$ から順に増やしながら両端点で未使用かどうかチェックし、$\Delta+1$ を超えた時点で貪欲の限界を報告する。

模範解答 (Python)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    edges = []
    degree = [0] * (N + 1)
    for _ in range(M):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        edges.append((u, v))
        degree[u] += 1
        degree[v] += 1

    delta = max(degree) if N > 0 else 0

    used_colors = [set() for _ in range(N + 1)]
    max_color_used = 0

    for (u, v) in edges:
        c = 1
        while c in used_colors[u] or c in used_colors[v]:
            c += 1
        if c > delta + 1:
            print(max_color_used)
            return
        used_colors[u].add(c)
        used_colors[v].add(c)
        max_color_used = max(max_color_used, c)

    print(max_color_used)

main()

Step-by-Step 解説

1辺彩色問題の定式化
頂点$v$に接続する辺は互いに全て隣接しているため、必要な色数は必ず最大次数$\Delta$以上になる。
2König's theoremとの対比
二部グラフに限れば辺彩色数はちょうど$\Delta$色（Class 1）で済むが、一般グラフでは奇閉路の存在などにより$\Delta+1$色が必要になる場合がある（例：奇数長サイクル）。
3単純貪欲法の限界
素朴な貪欲は必ずしも$\Delta+1$色に収まらない。真のMisra-Griesのアルゴリズムでは色衝突時にfan回転とKempe chain反転で必ず$\Delta+1$色以内に収める。
4最大次数の計算
各頂点の次数を数え上げその最大値$\Delta$を求める。$N\le7$なので最大次数は高々6。
5出力の意味
全辺が$\Delta+1$色以内で彩色できれば最大使用色番号を出力、途中で破綻すれば直前までの最大色番号を出力し、単純貪欲の限界を可視化する。

よくあるミス

ミス原因正しい書き方
$\Delta$を辺数$M$から誤って推定する次数の計算を怠り$M$や$N$で代用してしまう各頂点の次数を明示的にカウントし最大値を$\Delta$とする
色番号の探索上限を$\Delta$までにしてしまうVizingの定理の主張を誤解する探索は$\Delta+1$まで許容し、それを超えたら破綻とみなす
頂点彩色のアルゴリズムをそのまま流用してしまう辺彩色は線グラフの頂点彩色であることを忘れる各頂点ごとに接続する辺が使用中の色集合を管理する
貪欲法がΔ+1色で必ず成功すると誤解する定理の存在証明とアルゴリズムの構成的成功を混同するVizingの定理は存在を保証するのみで、真の構成にはfan回転とKempe chain反転が必要
自己ループや多重辺を考慮した実装にしてしまう制約を読み違える本問は単純グラフのみを扱う

次のステップ

  • 発展: Misra-Griesアルゴリズムの本体（fan回転 + Kempe chain反転）を実装し、$K_3$のような貪欲法が破綻するケースでも必ず$\Delta+1$色に収まることを確認せよ。
  • 次回予告: 簡潔ビットベクトル（Succinct Rank/Select、Jacobsonの階層的ブロック前計算）

自己評価

自分の回答

気づき・メモ