[logo] Web連載「数学ガールの秘密ノート」
Share

第296回 シーズン30 エピソード6
グラフ理論:表現と制約(後編)

登場人物紹介

:数学が好きな高校生。

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

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

$ \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\TRUE}{\textbf{true}} \newcommand{\FALSE}{\textbf{false}} \newcommand{\REMTEXT}[1]{\textbf{#1}} \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$ で塗った上で深さ優先で二彩色(咳)」

無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。

ひと月500円で「読み放題プラン」へご参加いただきますと、 423本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。


参加済みの方/すぐに参加したい方はこちら

結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加

(2020年7月10日)

[icon]

結城浩(ゆうき・ひろし) @hyuki


『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Twitter note 結城メルマガ Mastodon Bluesky Threads Home