情報系の知識を烏のように啄む

情報系の知識をたまに投稿します

グラフ理論 (2)

グラフ理論(1)に引き続き,今回は二部グラフを中心にまとめようと思います.

二部グラフとは?

二部グラフとは,グラフの頂点集合を二つのグループに分け,各グループ内に辺が存在しないようなグラフのことを言います.

f:id:t_ina17:20171129165310j:plain

グループがn個なら,n部グラフとも言います. 二部グラフには,二つのグループをまたぐ任意の辺が存在するグラフである完全二部グラフも存在する.

f:id:t_ina17:20171129165920j:plain

二部グラフの最大マッチング問題

グラフのマッチングとは,辺の両端に属する頂点が被らないように選択した辺集合である. 最大マッチングは,この辺集合の数が最大になるように選択したものである. 辺に重みがある場合は,辺集合の合計の重みが最大になるように選択する.(最大重みマッチング問題) 今回はその二部グラフの最大マッチングを扱おうと思います. 二部グラフの最大マッチングの応用先として,男女のカップル成立ペア検出など挙げられます.

f:id:t_ina17:20171129173727j:plain

男女のカップル成立ペアを太字で表示しています.

実際やってみる

辺に重みがついている場合で二部グラフの最大マッチング問題を実行してみようと思います.

設定として,男子5人,女子5人が存在し,お互いに相性のいいペアをなるべく多く見つける問題に取り組みます. グラフの頂点を男子,女子とし,男子はノード0~4のどれかに属します.女子はノード5~9に属します. 辺の重みをお互いの相性の良さとします.

お互いの相性の良さは実データがないので今回は1~10の整数値を乱数で取得したものを利用します. 以下のコードで設定の二部グラフを取得します.

import networkx as nx
from networkx.algorithms import bipartite
import numpy as np
import itertools
import matplotlib.pyplot as plt

group1 = range(5)
group2 = range(5,10)

node_color = ["b"] * 5
node_color.extend(["r"] * 5)

g = nx.Graph()
g.add_nodes_from(group1, bipartite=1)
g.add_nodes_from(group2, bipartite=0)

for (i,j) in itertools.product(group1, group2):
    val = np.random.randint(1, 10)
    g.add_edge(i, j, weight=val)

二部グラフを見やすくするために,男子のノードを左側に,女子のノードを右側に来るようにします. また相性の良さを辺の太さで表現します.

A,B = bipartite.sets(g)
pos = dict()
pos.update((n,(1,i)) for i,n in enumerate(A))
pos.update((n,(2,i)) for i,n in enumerate(B))

edge_width = [ d['weight']*0.3 for (u,v,d) in g.edges(data=True)]

nx.draw_networkx(g, pos, node_color=node_color)
nx.draw_networkx_edges(g, pos, width=edge_width)
plt.axis("off")
plt.show()

二部グラフを表示してみると以下のようになります.

f:id:t_ina17:20171129182734p:plain

次に,以下のコードでこの二部グラフを用いて最大重みマッチング問題を解きます.

d = nx.max_weight_matching(g)
for (i,j) in list(g.edges()):
    if (i,j) not in list(d.items()):
        g.remove_edge(i,j)

edge_width = [ d['weight']*0.3 for (u,v,d) in g.edges(data=True)]

nx.draw_networkx(g, pos, node_color=node_color)
nx.draw_networkx_edges(g, pos, width=edge_width)
plt.axis("off")
plt.show()

このコードではnetworkxのライブラリに入ってるmax_weight_matchingで最大重みマッチングで選択した辺集合を取得し,それ以外の辺集合を切断しています. 最大重みマッチングの結果は以下の図のようになります.

f:id:t_ina17:20171129182753p:plain

相性のいいペアが見つかってそうですね(適当

これは他の問題にも応用できるのでデータを手に入れ次第,やってみようと思います.