第296回 グラフ理論:表現と制約(後編)

三つ目の封筒には「機材予約の問題」が入っていた。問題を理解した「僕」とテトラちゃんとミルカさんがアルゴリズムを考える!

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

ミルカさん:数学が好きな高校生。 のクラスメート。長い黒髪の《饒舌才媛》。

$ \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\TRUE}{\textbf{true}} \newcommand{\FALSE}{\textbf{false}} \newcommand{\SET}[1]{\{\,#1\,\}} \newcommand{\EMPTYSET}{\{\,\}} $

図書室にて

いまは放課後。ここは高校の図書室。

と後輩のテトラちゃんは、クラスメートのミルカさんといっしょに村木先生から渡された問題を解いていた。

ミルカさんが持ってきた三つ目の封筒に入っていたのは「機材予約の問題」だった。(第295回参照)

《問題》(カード4)

管理スタッフであるあなたの前には、予約が集まっている。

この予約の集まりに対して、

  • 《割り当てが可能》ならば、少なくとも一つの割り当てを行い、
  • 《割り当てが不可能》ならば、不可能であることを示す。

このための手順を考案せよ。

(問題の背景は第295回参照)

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

同じ機材番号を予約したユーザを表す頂点を辺で結ぶ

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

予約の集まりからグラフができる

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

グラフが二彩色可能ならば、機材割り当ても可能である

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

グラフが二彩色不可能ならば、機材割り当ても不可能である

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

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

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

グラフの中に奇数長サイクルがあると二彩色不可能

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

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

テトラ「え?」

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

テトラ「ああ……」

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

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

ミルカ「straightforward」

彩色をどうすればいいか

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

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

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

通信網のグラフを二彩色した第294回参照)

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

ミルカ「?」

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

「そうだった」

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

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

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

《ごっつんこ》(色の衝突)第294回参照)

テトラちゃんは右上から、は左下から置いていった)

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

「うん、そうだね」

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

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

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

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

手順のスケッチ(1)

  • ある頂点をある色で塗る。
  • その頂点に隣接している頂点をその色とは異なる色で塗る。
  • それを繰り返す。

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

手順のスケッチ(2)

  • 一つの頂点$u$を色$c$で塗る。色$c$と異なる色を$d$とする。
  • 頂点$u$に隣接している頂点を$v$とし、頂点$v$を色$d$で塗る。
  • それを繰り返す。

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

「場合分け?」

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

「うん」

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

場合分けのスケッチ(1)

  • もしも頂点$u$が無色ならば、……
  • もしも頂点$u$が塗るべき色ですでに塗られていたならば、……
  • もしも頂点$u$が塗るべき色ではない色で塗られていたならば、……

テトラ「なるほどです」

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

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

場合分けのスケッチ(2)

  • もしも頂点$u$が無色ならば、塗るべき色で塗る。そして、頂点$u$から無色の頂点をたどっていける先の頂点もすべて塗る(★)。
  • もしも頂点$u$が塗るべき色ですでに塗られていたならば、何もしない。
  • もしも頂点$u$が塗るべき色ではない色で塗られていたならば、二彩色不可能。

「……」

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

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

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

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

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

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

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

「確かに」

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

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

リサが図書室にやってきた。 いつものように真っ赤なノートブック・コンピュータを小脇に抱えている。

彼女はミルカさんの呼び掛けに返事もせず、無表情で僕たちのところにやってきた。

登場人物紹介

リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。

僕たちがグラフの頂点を二彩色する手順を話すと、 リサは軽く頷いた。

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

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

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

リサ「できた」

リサのディスプレイを僕たちはのぞき込む。

COLOR-GRAPH

《アルゴリズムCOLOR-GRAPH》

入力

  • グラフ$G$

出力

  • グラフ$G$が二彩色可能ならば「グラフ$G$は二彩色できる」を返す。このとき、グラフ$G$の各頂点は白か黒かいずれかになっている。
  • グラフ$G$が二彩色不可能ならば「グラフ$G$は二彩色できない」を返す。

テトラ「え? たったこれだけですか? $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$で塗った上で深さ優先で二彩色(咳)」

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

複素数の世界に飛び込もう!世界をもっと広げよう!

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに12巻も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

chibio6 深さ優先探索にたいして、幅優先探索とはどんなプログラムなのだろうか。深度優先では頂点⑦の… https://t.co/C39xXxUphU 28日前 replyretweetfavorite

Lsdu2DalePerry 「メタ下校時間です」 約1ヶ月前 replyretweetfavorite

aramisakihime ステップごとの記録のところで、depth(深さ)の意味が腑に落ちました。ウォークスルーは楽しいですね(根気が要りますが)。 約1ヶ月前 replyretweetfavorite

strkmzw 学生の頃を思い出すなぁ。この連載ちょ~面白い。 https://t.co/LfwUCN4Pe8 約1ヶ月前 replyretweetfavorite