Julia(Graphs)で2部グラフかどうかを判別し、図示する方法

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

今回は、Julia(Graphs)で2部グラフかどうかを判別し、図示する方法を紹介します。

前提知識:グラフ理論における2部グラフ、マッチング、結婚定理とは

 

準備

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

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

 

簡単な例

まず、次のサイクルグラフを考えてみます。

 

「is_bipartite(グラフ)」で、グラフが2部グラフかどうか、trueかfalseで判定できます。

2部グラフでないとわかりました。

定義を確認しておくと、頂点の集合\(V\)が共通部分を持たない2つの集合\(V_1,V_2\)に分かれていて、\(V_1\)内、\(V_2\)内では異なる頂点が隣接しない(辺がない)グラフを、2部グラフ(bipartite graph)と呼んでいます。

 

別の例(スターグラフ)を考えましょう。

2部グラフであるとわかりました。

 

2部グラフに対しては、それぞれの頂点がどちらのグループ\(V_1,V_2\)に属するかが「bipartite_map(グラフ)」でわかります。

結果は16進数でわかりにくいかもしれませんが、下一桁の違い、1か2かが判定結果です。

 

この情報を使って、頂点の色塗り分けによって、グループ分けを図示しましょう。

各頂点の色のベクトルを、次のように与えます。もしグループ1ならば黄色、そうでないならば紫です。

 

この色ベクトルを使えば、2部グラフのようすがわかりやすくなります。

 

 

一般化

以上の結果を、一般化した関数を作りましょう。

 

この関数を使って、いくつかのグラフを2部グラフかどうか判定し、そうであるならば頂点を色分けして図示しましょう。

完全グラフ(complete graph)

 

ヒーウッドグラフ(Heawood graph)

同じグループの中で、隣接する頂点がないことを確認してみてください。

 

パップスグラフ(Pappus graph)

 

以上、Julia(Graphs)で2部グラフかどうかを判別し、図示する方法を紹介してきました。

明らかに2部グラフとして構成したグラフならばそうと判別しやすいですが、そうでないケースを目で判定するのは難しいです。そこでコンピュータで自動的に判定できると便利ですね。

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

 

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

 

こちらもおすすめ

グラフ理論における2部グラフ、マッチング、結婚定理とは