2 部グラフ判定

仲の悪い 2 人を、どうしても同じ班に入れてしまう

「この 2 人は別の班にしてください」という要望が何組か来ていて、班は 2 つしかありません。全部の要望を満たす分け方はあるでしょうか。あるなら分けたいですし、無いなら早く諦めて別の方法を考えたい。

要望を線で結んだ図が、そのままグラフです。線でつながった 2 人は必ず違う班へ。この条件で 2 つに分けられるグラフを 2 部グラフと呼びます。ユーザーと商品、学生と科目、ホームとアウェイのように、性質の違う 2 種類が向かい合う関係はたいていこの形をしています。

総当たりで班を割り振ると、40 人で 2 の 40 乗通りになります。実際にはそんなに試す必要はありません。1 人の班を決めた瞬間、その人と線でつながっている全員の班が自動的に決まるからです。

決まった人から、隣を反対に塗る

手順は単純です。まだ班の決まっていない人を 1 人選んで 0 番の班に入れます。その人の隣は全員 1 番の班。その隣は全員 0 番の班。こうして交互に塗り広げていきます。

反対の班は引き算 1 つで書けます。

塗り広げる途中で、すでに班の決まっている相手に出会います。そのとき見るのは 1 つだけです。相手の班が自分と 同じ なら、その時点で分けられません。違うなら、何もせず次へ進みます。この 2 つを枝分かれとして書き分けないと、すでに塗られた相手を上書きしてしまい、矛盾を見つける機会を失います。

三角形で試すと分かります。A を 0 番に、B を 1 番に、C は B の隣なので 0 番。ところが C は A ともつながっていて、A も 0 番です。ここで矛盾します。人数が奇数の輪があると、必ずこの形で行き詰まります。逆に 4 人の輪なら 0、1、0、1 と一周してぴったり閉じます。

全員を起点として一度ずつ見る

線でつながっていない人が別のところにいると、1 人から塗り広げただけでは全員に色が付きません。塗り残しがあるまま真を返すと、離れた場所にある三角形を見逃します。

外側で全員を順に見て、まだ色が付いていない人がいたら、そこから塗り直す。塊の数を数えたときと同じ形です。塊がいくつあっても、全体で 1 回ぶんの探索で片が付きます。

塗り分けの向きはどちらでもかまいません。ある塊の全員の班をそっくり入れ替えても、線でつながった 2 人が違う班であることは変わらないからです。ですから最初の 1 人を 0 番にするか 1 番にするかで悩む必要はありません。

なお、塗り分けはキューでもスタックでも書けます。色は隣との関係だけで決まるので、どの順に塗り広げても結果は同じです。

線が 1 本も無いときは、全員を片方に入れれば成立します。片方の班が空でもよいのか、と迷うところですが、「線でつながった 2 人が同じ班にいない」という条件は満たしているので成立します。

やってみよう

• 4 人の輪 (0-1-2-3-0) は分けられる。0、1、0、1 と塗って一周してみる
• 3 人の輪 (0-1-2-0) は分けられない。手で塗って、どこで詰まるか確かめる
• 5 人の輪も分けられない。奇数だから、という理由を自分の言葉で言えるか
• 要望が [[0,1],[1,2],[2,3]] のような一直線なら、必ず分けられる。輪になっていないから

1. BFS または DFS で 2 色塗り分けを試みること
2. 複数の連結成分にも対応すること (外側で全ノードをループする)
3. 隣接ノードが同色になった瞬間に False を返すこと