二部彩色と成分構造を扱う

概要

二部グラフの彩色と成分構造

無向グラフを二色に塗れる条件を探索で検証し、各連結成分の二部サイズ・反転対称性を集約する。

考え方

各辺の両端が違う色になるよう成分ごとに2色へ塗る。同色を要求する辺が見つかれば奇閉路の存在と対応して二部性が破れる。二部性の判定から左右の役割を持つmatchingへ進める。

各未訪問頂点を色0で開始し、辺u−vで未訪問vにはcolor[v]=1−color[u]を付け、訪問済みなら両色が異なるかを検査する。同じ色が見つかると、DFS/BFS木上の共通祖先までの道とその辺で奇閉路ができる。矛盾がなければ全辺が異色になり二部性を証明できる。各成分で色0・1の個数を数える。

連結成分のある頂点の色を固定すると、その全隣接色は強制され、全頂点へ伝わる。従って色付き表現は成分ごとの反転2通りだけで、C成分の非空graphには2^C通りある。ラベルの付いた頂点上で彩色を忘れる計数なら、この自由な反転による重複を補正できる。左右の役割・サイズを固定する問題では、反転しても同じ有効対象とは限らないため、無条件に2^Cで割らない。

成立条件と計算量

BFS・DFSでO(V+E)。非連結成分では色の左右を独立に反転できるため、数え上げで対称性を扱う。自己loopは即矛盾。無向graphの二部性を、有向辺の向きだけで決めない。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。二部性と部の反転対称性を扱い、連結二部グラフの彩色重複も補正する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: グラフアルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-bipartite-structure

習得する技能

  • 連結二部グラフの二つの彩色が部の交換だけで対応することを使い、彩色付きの計数から同じグラフの重複を補正できる。
  • 各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: 二部matching・Hall・Kőnig。

無向グラフを探索できることを前提に二部性と部の交換対称性を扱い、連結二部グラフの彩色重複も補正する。

このUnitでは扱わないもの

  • 重み付き最短路、一般の彩色問題、および容量付きmatching・min-cutの最適化。

根拠