Julia(Graphs)で全域木を求め、図示する方法

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

今回は、Julia(Graphs)で全域木を求め、図示する方法を紹介します。

前提知識:グラフ理論における全域木とは? その求め方

 

準備

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

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

 

全域木を求め、図示する方法

全域木とは

まず、与えられた連結なグラフ\(G\)の全域木(spanning tree)とは、すべての頂点を保ったまま、辺を部分的に取り除くことで得る木(グラフ)のことです。木(tree)とは、連結であり、サイクルを持たないグラフでした

一般に、グラフの全域木にはいくつかの候補があります。その中で辺の重みの合計が最も小さいものを、最小全域木(minimum spanning tree; MST)と呼びます。

今回は、各辺の重さが等しいケースでの最小全域木、つまり単に全域木のひとつを求めてみましょう。

 

簡単な例と関数作り

次の簡単なグラフを考えましょう。

 

「kruskal_mst(グラフ)」で、グラフの最小全域木がクラスカル法によって求められます。

辺をすべて取り除いたグラフに、サイクルが作られないようにひとつずつ辺を加えていく方法です。

 

結果を最短経路問題と同様にして図示してみましょう。

 

 

ブルグラフ(bull graph

 

正多面体グラフの最小全域木

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

 

正四面体

 

正六面体(立方体)

 

正八面体

 

正十二面体

 

正二十面体

 

以上、Julia(Graphs)で最小全域木を求め、図示する方法を紹介してきました。

図示すると、グラフがどんな全域木を持っているかわかりやすいですね。各辺の重みが異なるケースについては、別記事で紹介予定です。

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

 

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

 

こちらもおすすめ

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

グラフ理論における全域木とは? その求め方

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

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