Julia(Graphs)でハミルトンサイクルを求め、図示する方法

どうも、木村(@kimu3_slime)です。

今回は、Julia(Graphs)でハミルトンサイクルを求め、図示する方法を紹介します。

前提知識:グラフ理論における経路、連結性とは?Julia(Graphs)で最短経路問題を解き、図示する方法

 

準備

Graphs, GraphPlot, Colorsを使うので、持っていなければインストールしておきましょう。

準備として、以下のコードを実行しておきます。

 

ハミルトンサイクルを求め、図示する方法

ハミルトンサイクルとは

ハミルトンサイクル(Hamiltonian cycle)は、与えられたグラフのすべての頂点を一度だけ通るようなサイクル(単純な閉経路)です。ハミルトン閉路とも。

ハミルトンサイクルはいつでも存在するとは限りませんが、存在するときはグラフはハミルトングラフ(Hamiltonian graph)と呼ばれます。

重みつきグラフにおいて、その重さの合計を最小化するようなハミルトン経路を探す問題は、巡回セールスマン問題(traveling salesman problem)と呼ばれる有名な問題です。

目標とする複数の都市すべてを巡回したいセールスマンが、都市間の重み、例えば移動距離を最小化したい、という問題ですね。

巡回セールスマン問題において各辺の重みがすべて等しいケースがハミルトンサイクルを求める問題であり、ハミルトンサイクル問題の一般化が巡回セールスマン問題です。

 

ハミルトンサイクルの求め方

では、Juliaを使って具体的にハミルトンサイクルを求める方法を紹介しましょう。

まず、「simplecycles_limited_length(グラフ, n))」で、グラフに含まれる長さn以下の単純な(=頂点の重複がない)サイクル(正確には閉経路)がすべて求められます。

ハミルトンサイクルの長さはグラフの頂点数に等しいので、最大値として「nv(グラフ)」を指定しましょう。

長さ4以下のサイクルがすべて求められています。このうち、すべての頂点を通るサイクル、ハミルトンサイクルは、[1, 2, 4, 3]と[1, 3, 4, 2]ですね。

 

グラフのハミルトンサイクルを求める関数を作りましょう。

サイクルであって、その長さがグラフの頂点数に等しいものがあればそれがハミルトンサイクルなので、それを戻り値にします。

長さが2のものは閉経路ではありますが、サイクルとは呼びません。長さ3以上のものがないときは、空の配列を返す仕様です。

 

ハミルトンサイクルのひとつが求められました。

 

ハミルトンサイクルの図示

ハミルトンサイクルをよりわかりやすく理解するため、辺に色をつけたプロットによって図示しましょう。

そのために、Hamiltonian_cycleの数ベクトルを、SimpleEdge型のベクトルに変換します。空のグラフにHamiltonian_cycleの情報を使って辺を加えていき、collect(edges(GE))で辺をまとめます。

 

辺(SimpleEdge)のベクトルを使えば、最短経路問題と同様にして、辺に色をつけてプロットできます。

ハミルトンサイクルが一目瞭然ですね。

 

一般形

以上の結果を一般化して、ハミルトンサイクルを求め、それを図示する関数を作りましょう。「Hamiltonian_cycle」の長さが3以上ならプロットし、それ以下ならば「ハミルトンサイクルは存在しない」と表示することにします。

 

ハミルトンサイクルが存在しない例

ケーニヒスベルクの橋のグラフについて調べてみましょう。

 

このグラフがハミルトングラフでないことがわかりました。

 

正多面体グラフのハミルトンサイクル

プラトン立体(正多面体)のグラフは、すべてハミルトングラフであることが知られています。それを確かめてみましょう。

Graphs.jlでは、smallgraphという関数でプラトン立体のグラフが作れます。

 

正四面体

 

正六面体(立方体)

 

正八面体

 

正十二面体

これは、数学者のハミルトンがハミルトンサイクル問題を最初に考えた例と言われています。

 

正二十面体

 

 

以上、Julia(Graphs)でハミルトンサイクルを求め、図示する方法を紹介してきました。

ハミルトンサイクルが存在するかどうかを決定する一般的な問題は、グラフのサイズが大きくなると時間がかかります。計算複雑性の理論では、ハミルトンサイクル問題はNP完全、巡回セールスマン問題はNP困難です。

実際、頂点数50、辺の数1000を持つあるグラフのsimplecycles_limited_lengthを実行すると、約2秒かかる上に、サイクルの一部しか求められていません。simplecycles_limited_lengthで求められるサイクルの数の上限は、10^6=100万です。(より速く、サイズの大きな問題に適した方法があるかもしれません。)

それでも、プラトン立体のグラフ程度の問題ならば、合計で1秒程度で図示もできるので、ぜひ試してみてはいかがでしょうか。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

1から始める Juliaプログラミング
進藤 裕之(著), 佐藤 建太(著)
コロナ社 (2020-03-26T00:00:01Z)
5つ星のうち4.5
¥7,353 (コレクター商品)

 

こちらもおすすめ

グラフ理論における経路、連結性とは?

Julia(Graphs)で最短経路問題を解き、図示する方法

重み付きグラフ、最小全域木の問題とは? クラスカル法による解き方