-Maxima入門- グラフ理論パッケージの使い方

f:id:jurupapa:20070811114721j:plain

ご機嫌

普段あまり使わないパッケージを触ってみるのも楽しいです。という訳で今回はグラフ理論パッケージgraphsの紹介です。グラフとありますが、x軸とy軸がある関数のグラフではなく、頂点と辺からなるグラフの方です。

まずはパッケージを読み込みます。これでマニュアル58. graphsに記載されている関数を全て使えるようになります。

(%i1) load(graphs)$

早速グラフを一つ作ってみます。create_graph()に頂点の数と、頂点の組による辺の情報を与えれば、任意のグラフを作ることができます。

ここでは三角形に尻尾が１本生えているようなグラフを作ります。

(%i2) g1:create_graph(4,[[0,1],[1,2],[2,3],[3,1]]);

$\tag{%o2} \verb|GRAPH(4 vertices, 4 edges)|$

描画してみましょう。それにはdraw_graph()という関数を使います。
(%i3) draw_graph(g1,show_id=true,text_color=white);

f:id:jurupapa:20150429001105p:plain

$\tag{%o3} \mathbf{done}$

Graphパッケージにはよく知られたグラフを一発で生成する関数が多数収録されています。その中の一つがn次元立方体グラフの生成関数cube_graph(n)。これを使って3次元立方体のグラフを生成します。
(%i4) g2:cube_graph (3);
$\tag{%o4} \verb|GRAPH(8 vertices, 12 edges)|$

早速描画してみましょう。
(%i5) draw_graph(g2,show_id=true,text_color=white);

f:id:jurupapa:20150429001630p:plain

$\tag{%o5} \mathbf{done}$

折角ですので、このハミルトン閉路を求めてみます。あるグラフのハミルトン閉路とは、そのグラフの全ての頂点を一度づつ訪れて、最初の頂点に戻るような経路のことです。hamilton_cycle()という関数で求められます。
(%i6) hc:hamilton_cycle(g2);
$\tag{%o6} \left[ 7 , 3 , 2 , 6 , 4 , 0 , 1 , 5 , 7 \right]$