ハミルトンパスは難しい!!!

で、今日はだからそっちの双対ではなくて、オイラーパスに対して今度はハミルトンパスっていうのを考えてみます。
で、それのためには、ハミルトン閉路っていうのは、各点をちょうど一度づつ通る、こっちはこれもだからHamilton卿が考えたからこういう名前が付いてるわけですが、今度は点になってるわけですね。
だから、ちなみにeulerの場合は、オイラー閉路はなんだったかと言うと…こういうのはかっこいい双対ではなくて、単にこう問題として対応するでしょっていう…各枝だったんですよね。

で、今日ここまでやったのはオイラー閉路っていうのは次数っていうことに着目することによって実はlinear timeでまずチェックができるわけですね。各数の次数が偶数かどうかなんてのはlinear timeでチェックできるわけです。
でしかも、実際に今やったアルゴリズムっていうのは、リストをちゃんと扱うことさえ知っていれば、ちゃんとlinear timeのimplementationができます。

で、それに対してこれメチャクチャ似てる問題ですよね。
で例えば、あたり前なんですけど、完全グラフは必ずハミルトン閉路を持ちますよね。これK5です。planerでない代表選手でしたよね。これ、完全グラフですよ。完全グラフは必ずハミルトン閉路を持ちますよね。
えーとこっからスタートして、点に1、2、3、4、5、6、7、8、9、…nって付けて置くとこれで大丈夫ですよね。だってどの2点の間にも枝があるんだから、こう、ちゃんと閉路でたどれるでしょ。

[ハミルトン1]

でも例えばこれ、こういう風に、10点のグラフにします。これpetersonグラフっていうんですけど、これハミルトン閉路がありそうでしょ?
まずはまあ、みんなはまずはめのこでやって、これあるよね。
ま、これもある意味で代表的なグラフなんですけど、名前が付いてるグラフですから。少なくともこれ外周をぐるっと回ってしまうと、後ここへ戻ってしまうと2回通っちゃいますよね。
ちょうど一度づつですからここ入っちゃいますよね。で、こうなったら普通こういってこういってこうってこういっちゃいますから、ここでどんづまりですよね。
閉路にはならないですよね。ハミルトンパスは存在するけれども、閉路じゃなかったわけですね。
ちなみにあるかどうかはみんな、じっと考えて下さい。

こういうのをさらに一般化すると,各枝に長さがついたときに、ハミルトン閉路の中で一番長さの短いものを求める問題が生じます。
これは、巡回セールスマン(商人)が各都市をちょうど一度ずつ訪ねて戻ってくる最短路を求める問題に対応していることから,巡回商人問題(Tranveling Salesman Problem; TSP)と呼ばれ、難しい問題の代表選手になってるわけです。
それで、よく新聞などでもこの巡回商人問題を解いたなんていうのが出るわけです(こういうのは気をつけて読まないといけないけど)。


きょうのまとめ

で、今日講義で最後に言いたいのは、今日ここまで話したのは簡単な話でしたよね。だから例えば、学部の講義でこの3学年の間で離散数学っていうのはこういうかっこいい離散構造の話をします。
あまりにも今日は簡単すぎたかも知れないけど、まずは例えばその代表選手がeulerグラフなわけです。で、計算量の世界では、でも離散構造っていうのは結局はしらみつぶしに調べあげないと解けなくて、で、そのしらみつぶしに調べあげる対象っていうのは普通はexponentialにblow upしてくわけですね。指数爆発をする。組み合 わせ爆発をする。
で、そうするといくら速かろうが、絶対手に負えないんですね。

実際にそういうのはですね、例えばハードウェア構成法なんかで、論理回路の最小化なんていうのが出ますから、別に関係ない講義ですよね、でもそこでやるっていうのは何かっていうと、論理関数の最小化っていうのはまず最初に組み合わせ爆発するので有名な問題なわけですね。
で、それみんながまじめに例えばですね。100素子ぐらいの論理回路を最小化しようとしたら、みんながボンってやったらですね、学科の計算機が全部ダウンして、みんな学科の計算機使えなくなっちゃうぐらいに、負荷がかかるわけです。
で、とてもじゃないけど学科の計算機全部を一度に使っても解けるような問題じゃないわけですね。数千素子の元の論理回路の最小化をみんなが知ってる程度のアルゴリズムでやろうとすると。
で、とにかくそういう難しいのがあるらしいわけです。

で、今日はとにかく代表選手として簡単な問題をやりましたので、特徴付けも非常にきれいだし、linear timeで条件をチェックできるし、実際に求めることもできた。
で今はこれ単に枝を点に変えただけですよね。で、今これはまあ、めのこでどうやら無さそうだというわけですね、ハミルトン閉路が。
で、実はだから、こういうことが離散構造が本当に顕著なんですけども、たかがこの違いだけ、たかが枝を点に変えただけで実はこっちはそのintractableな世界に入るというわけです。
ハミルトン閉路というのはintractableの欄に書きましたよね。で、こういうのは与えられたグラフがハミルトン閉路を持つかどうかを指数爆発なしに、多項式時間で解けるかっていうのは、一大未解決問題で、計算量理論ではこれをNP完全な問題、NP-hardな問題であるっていうことは証明して、難しそうであることは証明しているんですけれども、実はそれは本当に一大未解決問題なんですよね。

で、離散構造っていうのはこういう感じで、構造が良ければ簡単に解けちゃうんだけれども、一度なんかくずれてしまうと、これはもう手に負えないんですね。intractableな問題になる。
もちろんこんな小さければですね、hamiltonianの問題、つまり…、で実際これはですね、グラフ理論的にもグラフがhamiltonian circuitを持つための、必要かつ十分条件… 今の場合これ非常に簡単な非常にきれいな特徴づけでしたよね…で、そういうのは実は知られてないんですね。
で、逆にそういうきれいなcharacterizationがあれば、アルゴリズムっていうのは何とかなるっていうのがこれまで経験則なわけです。

で、今日はまだまだ何回も言うように、これだけ、この程度だけだったらば、あまりにも簡単だったから、あの黒板一枚で証明が終わるぐらいだったからあまりにも簡単すぎたけど、それだけじゃなくて、もう少し複雑なんだけども、やっぱり結局、よくよく考えてみるとなんか、さっき言ったようなキーワード、双対なんていう何かmagicがあって、まだそうか、双対なんていうのはわかんないと思うんですけど、そういう構造が成り立つと、非常に効率良く解けてしまうんですね。
で、それが、例えば最大流とか、最小費用流とか、あるいはパーフェクトグラフっていうののカラーリングとか、クリークとか、独立点集合とか、そういう話なわけです。
で、今言ったこと全部ちんぷんかんぷんですよね。で、もちろんそれはちんぷんかんぷんで今はいいわけで、それを前期の離散数学の講義でやっていきます。
で、後期の計算量ではこういう難しい問題、で、こういうのパズルでよく見るでしょ。つまりこれは結構難しいわけですよね、本当に。
で、そういう難しさを示す量と同時に、でもそういう難しい問題をどうやってタックルしていくかっていうのを計算量の講義でやるわけです。

で、今日はまだまだお絵書きの話で、あまりにも簡単な、でもかっこいい、グラフ理論の一番スタートの問題からやっていったわけですが、次回はもう少し2部グラフの話をして、えっと、次回最後ぐらいからだんだんフローの話に入って、一度わりと抽象的な、わりと高いレベルの話をしておいて、そこからまた降りてきて、今日はあんまりちゃんと言ってない連結性の話とか、あとマッチング、そのダンパの時の組み合わせのメーキングの話ですけど、そういう話をやっていきます。
じゃ、ま、こんぐらいで今日は。まだまだ第一週ですのでみんな大変ですけど、がんばって。

おしまい


Prev

 

〔トップページへ〕 〔離散数学の仮想講義のindexページへ〕
<vu@is.s.u-tokyo.ac.jp>

Last updated on 11 May, 1999