第296回 シーズン30 エピソード6

グラフ理論：表現と制約（後編）

図書室にて

僕「……だから、 ユーザを頂点として、同じ機材番号を予約したユーザ……つまり予約が衝突しているユーザのあいだを辺で結ぶ」

僕「そうすると、予約の集まりからグラフができる」

僕「そのグラフの頂点を二色で塗り分けられる……つまり、二彩色可能ならば、機材割り当ても可能になる」

僕「二彩色不可能ならば、機材割り当ても不可能になるというわけだね」

ミルカ「二彩色グラフは二部グラフだから《二部グラフの判定条件》がそのまま使えるな」

テトラ「あっ、きっ、奇数長サイクルの存在！！」

僕「そうか！　そうだよね！　 《奇数長サイクルの存在》と《二彩色不可能》とは同値なんだ。 グラフの中に奇数長サイクルがあるかどうかを調べればいい！」

テトラ「できましたね！」

ミルカ「いや、違う。私たちはいまようやく問題を理解したのだ」

テトラ「え？」

僕「問われているのは、判定条件じゃなくて、割り当てを実際に見つける手順だから……だね」

テトラ「ああ……」

ミルカ「ふむ。しかし、手順は簡単じゃないか？」

テトラ「そ、そうなんですか？　easy?」

ミルカ「straightforward」

彩色をどうすればいいか

僕「ユーザを頂点として、予約が衝突している二人が隣接するように辺を定めて……うん、 あとは制約に違反しないように施設を割り当てていけばいいんだよ。つまり、グラフの頂点に色を塗っていくんだね」

テトラ「それは、もしかしてあたしと先輩が、未来都市の通信網のグラフにオセロの石を並べたように？（第294回参照）」

僕「そうそう！　まさにそうだね。頂点の上に白か黒の石を置いていくけど、辺の両端には必ず白黒別の石を置いていくんだ。 『二色で塗る』といっても、『別の施設を割り当てる』といっても同じことだね。 表現の仕方が違うだけで」

テトラ「あっと、でも、あのときは《ごっつんこ》がありましたね……」

ミルカ「？」

テトラ「あ、はい。あたしと先輩はそれぞれ頂点に色を塗っていきました。 つまりオセロの石を置いていきました。 でも途中で、一つの頂点をあたしは白にしたくて、でも先輩は黒にしたかったんです。 色の衝突です」

僕「そうだった」

テトラ「《ごっつんこ》……衝突したので、あたしはそれまでに置いた石をすべて反転してから作業を続けたんです。 ということは、手順をきちんと表現するのはなかなかたいへんですね」

ミルカ「む？　一つの頂点を別の色で塗る必要が生じたら、 そのグラフは二彩色不可能じゃないのか？」

僕「ああ、違うよ、ミルカさん。 あのときは、僕とテトラちゃんが一つのグラフを別の箇所から塗り始めたんだ。 かなり間抜けな話だけど」

ミルカ「そういうことか。手分けするにしても、すでに色を塗った頂点から始めるべきだったな。 塗り進めている部分グラフが常に連結になるように保ちつつ進む」

僕「うん、そうだね」

ミルカ「そのようにすれば、テトラのいう『すでに塗った頂点を塗り直す』必要はないはずだ」

テトラ「だとしたら……グラフの頂点に色を塗っていくようすを素直に手順にすればいいんでしょうか……」

二彩色の手順をスケッチする

テトラ「……たとえば、こんな感じではどうでしょう」

僕「うーん……これだと『ある頂点』とか『ある色』とか『その頂点』みたいになってしまうと混乱するから、 名前を付けた方がいいんじゃないかな。こんなふうに」

ミルカ「ふうん……これでは『それを繰り返す』の『それ』が不明確だし、 色 $c$ をどうやって決めるかもわからないし、場合分けも不十分」

僕「場合分け？」

ミルカ「頂点には三種類ある。 まだ色を塗っていない……いわば無色の頂点。それから白の頂点。そして黒の頂点」

僕「うん」

ミルカ「それぞれで処理が変わるはずだ。 しかし、二彩色で考えるには《白か黒か》よりも、 《塗るべき色か否か》が大事だから、こんな場合分けになるだろう」

テトラ「なるほどです」

僕「そうか。これなら考えに抜けがなくなるか」

ミルカ「問題は場合分けの先の処理。つまり《ならば》の先で何をするかだが……こうかな」

僕「……」

ミルカ「これで、頂点 $u$ を含む連結成分が塗れる。 もしかしたら与えられたグラフには他の連結成分があるかもしれないから、 また新たに無色の頂点を決めるところからリスタート」

テトラ「あれ、ちょっとお待ちください。またわからなくなりました。 色が《ごっつんこ》……衝突してしまったときに、 片方の色を反転させるというのはほんとうにいらないんですか？」

ミルカ「いらない。 ★では色を塗り進めていく。 その途中では、色が塗られた頂点が次第に増えていく。 色が塗られた頂点だけを集めて部分グラフを作るなら、それは連結している。 だから、色を塗り進める途中で、塗るべき色ではない色で塗られているものがあったら、 即座に二彩色不可能といえる。 連結成分の中に奇数長サイクルが含まれたことになるからだ」

僕「テトラちゃんと僕が二手に分かれてオセロの石を置いたときは、 色が塗りかけの頂点を集めて作る部分グラフが連結していなかったんだね」

テトラ「え……でも、★では無色の頂点をたどっていくんですから、 塗るべき色ではない色で塗られている頂点にはぶつからないのでは？　……わからなくなりました！」

ミルカ「やはり、単なるスケッチでは議論ができない。 グラフの頂点を二色で塗るアルゴリズムをきちんと書く」

テトラ「アルゴリズム！」

僕「確かに」

グラフの二彩色アルゴリズム

ミルカ「ちょうどいい、リサがやってきた。手伝ってもらおう。リサ！」

リサ「DFSを再帰で書けば、すぐにできる（咳）」

テトラ「DFSって何ですか」

ミルカ「Depth First Searchのアクロニム。深さ優先探索」

リサ「できた」

COLOR-GRAPH

テトラ「え？　たったこれだけですか？　 $11$ 行？」

リサ「これは途中」

僕「G1は、手続きの名前だね。COLOR-GRAPH(G) でグラフ $G$ を二彩色する」

リサ「戻り値は、二彩色可能か不可能か（咳）」

テトラ「G2では、頂点を無色にしています。なるほどです。最初に無色にしておくのは気付きませんでした」

ミルカ「確かにそうだな」

リサ「初期化」

僕「G3からG9まではforeachの繰り返しがあるけど、これはグラフ $G$ の頂点すべてについての繰り返しということだよね。 毎回一つ頂点を選んでそれを $v$ とする、ということでいいの？」

リサ「（頷く）」

テトラ「G4では、もしも頂点 $v$ が無色だったら……というifがあります。そしてさらにG5ではもう一つのifがあって、 そこにCOLOR-DFSというものが出てきました。ややこしいですね。そもそも、どうしてG4でわざわざ頂点 $v$ が無色かどうかを調べているんでしょう。 さっき無色にしたばかりですよね」

ミルカ「手続きCOLOR-DFSの中で、その頂点が塗られているかもしれないから。 否定の $\lnot$ があるから、COLOR-DFSが偽になったら、塗ることに失敗したことを意味する」

僕「ということは、鍵となるのはCOLOR-DFSで何をするか、だね」

アルゴリズムCOLOR-DFS

リサ「COLOR-DFSは、頂点 $u$ を色 $c$ で塗った上で深さ優先で二彩色（咳）」