Julia(Graphs)で重み付きグラフの最小全域木を求め、図示する方法

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

今回は、Julia(Graphs)で重み付きグラフの最小全域木を求め、図示する方法を紹介します。

前提知識:Julia(Graphs)で最小全域木を求め、図示する方法

 



準備

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

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

 

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

最小全域木とは

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

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

この問題は、送電網やネットワークの効率化に応用できるものです。

 

簡単な例と関数作り

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

重みベクトルによって、各辺に重みを指定しています。

今回は、1以上5以下の整数をランダムに与えました。乱数のシードを指定することで、実行結果は再現されます。

 

最小全域木を求めるためには、重みベクトルを距離行列に変換する必要があります。

 

例えば、今回与えた距離行列は、次のようなものです。

 

「kruskal_mst(グラフ, 距離行列)」で、重み付きグラフの最小全域木がクラスカル法によって求められます。

辺をすべて取り除いたグラフに、サイクルが作られないようにひとつずつ辺を加えていく方法です。辺を加える順序として、重みが小さい順に並べ替えておきます。

 

求められた最小全域木の重み合計を計算する関数を作りましょう。

 

 

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

 

このグラフには他にも全域木がありますが、それと比べても辺の重み合計が最小となっていることがわかりますね。どの辺を1つ付け替えても、必ず重みの合計は増えてしまいます。

 

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

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

辺に1から5までのランダムな整数の重みを与え、最小全域木を求めてみましょう。

 

正四面体

 

正六面体(立方体)

 

正八面体

 

正十二面体

 

正二十面体

 

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

プラトン立体の結果をすべて表示するのに1秒かからず、目で見てわかるグラフが得られるのは便利ですね。

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

 

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

 

こちらもおすすめ

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

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

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

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

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