XXIV-th stone: edge searching

さて、先生と議論の結果、昨日言っていたように、巷では解けているのだが、今回の結果にも意義がないわけではないので、修士論文の内容としては適当なのでは。という結論にいたった。ということは？修論の内容決定ということですよ♪この内容で修論書いていいってことです。大変嬉しい。研究というのは期限内にやれといわれてやるものではないと私は思っている。しかし期限なしでは何も結果なしで「下手のよこずき」というかただ好きなことをしているというだけになってしまう。しかし、この修論では外に発表しにいけるレベルの結果ではないので別の方法を考えなくては。

それに関して今日面白い問題を見つけたので紹介する。まず、無向グラフG=(V,E)が与えられる。問題は以下のとおりだ。
[edge searching game]
G＝（V.E)中のすべての辺が有毒ガスで汚染されている。以下の手順を繰り返し用いて、すべての辺をclearにするにはどうすればよいか？
また、clearerの最小人数は何人だろうか？一度clearになったら再度汚染されることはないとし、clearになったedgeは後戻りはできないとする
a)ひとつの頂点に新しいclearerを配置する
b)頂点からclearerを削除する
c)clearerを辺にそって移動させる。(汚染された辺の一方の端点にclearerがいてそれをその辺にそって動かしたとき、その辺はclearになる)

適当なグラフを自分で書いて調べてみるとおもしろいとおもう。自明であるが一筆書きできる図形はes(G)=1となる。実はこのclearerの最小数をedge searching numberといいes(G)と記す。この値はグラフのpath-width(pw(G)),またはproper-path-width(ppw（G))と非常に深い関連をもっており、graph のVLSI　layoutを考える上で非常に重要なパラメータになっているのである。