Maxima で綴る数学の旅

紙と鉛筆の代わりに、数式処理システムMaxima / Macsyma を使って、数学を楽しみましょう

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

f:id:jurupapa:20070811114721j:plain

ご機嫌

にほんブログ村 科学ブログ 数学へ
にほんブログ村

 

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

 

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

(%i1) load(graphs)$

 

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

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

(%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]

3次元立方体のグラフにそのハミルトン閉路を重ねたものを描画します。
(%i7)

draw_graph(g2,show_edges=vertices_to_cycle(hc),show_id=true,text_color=white);

f:id:jurupapa:20150429001929p:plain


 \tag{%o7} \mathbf{done}

グラフ理論パッケージの紹介は次回に続きます。

This is a test.
天気