2 部グラフと奇閉路

頂点を 2 色に塗り分けて 2 部グラフかどうかを判定できる。「2 部グラフ $⟺$ 奇数長の閉路をもたない」を使って、判定の根拠を示せる

前提

グラフの次数と握手補題（大学数学グラフ理論）

この技能までの道筋（6 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）

説明

グラフの頂点を 2 色で塗り、どの辺も異なる色の頂点を結ぶようにできるかを調べます。これで、そのグラフが 2 部グラフかどうかを判定できます。2 部グラフであれば塗り分けそのものが根拠になります。そうでなければ、奇数長の閉路を 1 つ示すことが根拠になります。割り当て問題・マッチング・スケジューリングなど、対象を 2 つのグループに分ける場面でよく使います。

なぜそうしてよいのか

ここでは、ループ（同じ頂点を結ぶ辺）や多重辺のない単純グラフ $G = (V, E)$ を考えます。まず用語を決めます。
- 歩道：頂点の列 $v_{0}, v_{1}, \dots, v_{k}$ で、隣り合う $v_{i - 1}, v_{i}$ がいつも辺で結ばれているもの。同じ頂点を何度通ってもかまいません。辺の数 $k$ を長さといいます。
- 閉じた歩道： $v_{k} = v_{0}$ となる歩道。
- 閉路：閉じた歩道のうち、 $k \geq 3$ で、 $v_{0}, v_{1}, \dots, v_{k - 1}$ がすべて異なるもの。頂点の重複を許さない点が、閉じた歩道との違いです。
- 連結：どの 2 頂点も歩道で結べること。
- 連結成分：ある頂点から歩道でたどり着ける頂点をすべて集めたもの。グラフは、互いに辺で結ばれていない連結成分に分かれます。
- 最短距離 $d (u, v)$ ： $u$ から $v$ への歩道の長さの最小値。

$G$ が 2 部グラフ であるとは、 $V$ を共通部分のない 2 つの集合 $A, B$ に分けて、どの辺も $A$ の頂点と $B$ の頂点を結ぶようにできることです。 $A$ を白、 $B$ を黒と塗れば、「隣り合う頂点がいつも違う色になる 2 色の塗り分けがある」ことと同じ意味になります。

(⇒) 2 部グラフで閉路をたどると、1 辺進むたびに色が白・黒と入れかわります。出発点と同じ色に戻るには偶数回入れかわる必要があるので、閉路の長さは必ず偶数です。したがって、奇数長の閉路はありません。

(⇐) 奇数長の閉路がないとします。連結成分ごとに頂点 $r$ を 1 つ選び、 $d (v) = d (r, v)$ とおきます。 $d (v)$ が偶数の頂点を白、奇数の頂点を黒と塗ります。両端が同じ色の辺 $uv$ があったとして、矛盾を導きます。
- $r$ から $u$ への長さ $d (u)$ の歩道に辺 $uv$ を足すと、 $v$ への長さ $d (u) + 1$ の歩道になります。よって $d (v) \leq d (u) + 1$ です。同じように $d (u) \leq d (v) + 1$ なので、 $∣ d (u) - d (v) ∣ \leq 1$ が成り立ちます。
- 一方、 $u, v$ は同じ色なので $d (u)$ と $d (v)$ の偶奇は一致し、差は偶数です。したがって $d (u) = d (v) = d$ となります。
- このとき、「 $r$ から $u$ への最短の歩道 → 辺 $uv$ → $v$ から $r$ への最短の歩道」は、長さ $2 d + 1$ （奇数）の閉じた歩道です。

奇数長の閉じた歩道から、奇数長の閉路を取り出せることを示します。途中で同じ頂点を 2 度通っていれば、そこで 2 つの短い閉じた歩道に切り分けます。2 つの長さの和は奇数なので、どちらか一方は奇数長です。その奇数長の方について同じ操作を繰り返すと、長さは毎回短くなるので、やがて頂点の重複がない奇数長の閉じた歩道が残ります。ループがないので長さ 1 はありえず、長さは 3 以上です。よってこれは奇数長の閉路であり、仮定に反します。したがって、この塗り方で正しく塗り分けられます。

以上から「2 部グラフ $⟺$ 奇数長の閉路をもたない」が成り立ちます。実際の判定では最短距離を計算しなくてよく、「隣の頂点には反対の色を塗る」ことを広げていけば十分です。こうして塗った頂点は、出発点からの歩道で 1 辺ごとに色が入れかわっています。そのため、同じ色の頂点の間で矛盾が起きたときも、上と同じ偶奇の議論で奇数長の閉じた歩道が得られます。

手順

連結成分を 1 つ選び、その中の頂点を 1 つ選んで色 A を塗る。
色を塗った頂点の隣で、まだ塗っていない頂点に、反対の色を塗る。これを、その成分のすべての頂点が塗られるまで繰り返す（連結成分の中では、色は強制的に決まっていく）。まだ塗っていない成分があれば、手順 1 に戻る。
すべての辺について、両端の色が異なるかを確かめる。
両端が同じ色の辺 $uv$ が見つかったら、2 部グラフではない。出発点から $u$ へ塗り広げた歩道と、 $v$ へ塗り広げた歩道の長さは偶奇が同じである。そこで「出発点 → $u$ → 辺 $uv$ → $v$ → 出発点」とたどると、長さが（偶数） $+ 1$ の奇数長の閉じた歩道ができる。その中から奇数長の閉路を取り出して、根拠として示す。
どの辺も両端の色が異なれば、2 部グラフである。色 A の頂点の集合と色 B の頂点の集合が、求める 2 つの組 $A, B$ になり、この塗り分けそのものが根拠になる。

例題

頂点集合 $V = {1, 2, 3, 4, 5, 6, 7}$ 、辺集合 $E = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 1}, {1, 4}, {3, 6}, {2, 7}, {6, 7}}$ のグラフ $G$ は連結である。 $G$ が 2 部グラフであることを確かめよ。また、頂点を 2 色に塗り分けたとき、頂点 $1$ と同じ色になる頂点の集合（頂点 $1$ 自身を含む）を求めよ。

例題の解答

手順 1: $G$ は連結なので、連結成分は 1 つだけである。頂点 $1$ に色 A を塗る。
手順 2: $1$ の隣は $2, 4, 6$ なので、これらに B を塗る。 $2$ の隣でまだ塗っていない $3, 7$ に A を塗る。 $4$ の隣でまだ塗っていない $5$ に A を塗る。これで全頂点が塗られ、A は ${1, 3, 5, 7}$ 、B は ${2, 4, 6}$ となる。
手順 3: 全 10 本の辺について両端の色を確かめる。 ${1, 2}$ : A–B、 ${2, 3}$ : B–A、 ${3, 4}$ : A–B、 ${4, 5}$ : B–A、 ${5, 6}$ : A–B、 ${6, 1}$ : B–A、 ${1, 4}$ : A–B、 ${3, 6}$ : A–B、 ${2, 7}$ : B–A、 ${6, 7}$ : B–A。どの辺も両端の色が異なる。
手順 5: 両端が同じ色の辺はないので、 $G$ は 2 部グラフであり、 $A = {1, 3, 5, 7}$ 、 $B = {2, 4, 6}$ と分けられる。したがって、 $G$ は奇数長の閉路をもたない。また $G$ は連結なので、頂点 $1$ の色を決めると、他の頂点の色は「隣は反対の色」によってすべて強制的に決まる。よって、頂点 $1$ と同じ色の頂点の集合はただ 1 通りに定まり、 ${1, 3, 5, 7}$ である。

答え: ${1, 3, 5, 7}$

よくある誤り

三角形（長さ 3 の閉路）がなければ 2 部グラフだとしてしまう誤り。正しくは、長さ 3, 5, 7, … のすべての奇数長の閉路がないことが必要。たとえば $C_{5}$ は三角形をもたないが、長さ 5 の閉路があるので 2 部グラフではない。
偶数長の閉路があること、または頂点数や辺数が偶数であることを理由に、2 部グラフだとしてしまう誤り。たとえば $K_{4}$ は頂点数 4、辺数 $\frac{4 \cdot 3}{2} = 6$ で長さ 4 の閉路ももつが、三角形があるので 2 部グラフではない。正しくは、奇数長の閉路が 1 つもないことを確かめる。実際には、塗り分けを最後まで行えばよい。
隣り合っていない頂点どうしの色を先に勝手に決め、途中で矛盾したので『2 部グラフでない』としてしまう誤り。正しくは、各連結成分で最初の 1 頂点だけ色を選び、残りは『隣は反対の色』の規則だけで決める。こうして生じた矛盾だけが、奇数長の閉路の根拠になる。たとえば $C_{4}$ （辺 ${1, 2}, {2, 3}, {3, 4}, {4, 1}$ ）で $1$ と $3$ を別の色にすると矛盾するが、 $C_{4}$ は 2 部グラフである。
グラフが連結でないのに、1 つの連結成分だけを調べて結論を出してしまう誤り。正しくは、すべての連結成分で塗り分けを行う。どれか 1 つの成分に奇数長の閉路があれば、グラフ全体は 2 部グラフではない。たとえば $C_{4}$ と $C_{3}$ を並べたグラフは、 $C_{4}$ の部分だけ見れば塗り分けられるが、全体としては 2 部グラフではない。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

ハミルトン閉路の有無（大学数学グラフ理論）
最大マッチングとケーニヒの定理（大学数学グラフ理論）
頂点彩色と彩色数（大学数学グラフ理論）
平面グラフとオイラーの公式（大学数学グラフ理論）