マッチング（NetworkX）

問題

ある男女10人のグループがあり、男女間には好意があると仮定します。

このグループを、男女のペアを作ることができるようにマッチングさせることを考えます。

ただし、それぞれの男性・女性が同時に複数の異性とのペアを持てないものとします。

---

以下の男女間の好意度が与えられています。

この好意度を最大化するように、マッチングを決定してください。

	男１	男２	男３	男４	男５
女１	70	90	80	80	70
女２	60	10	80	70	60
女３	70	70	100	70	60
女４	80	80	80	50	60
女５	90	90	90	90	30

解法

NetworkXライブラリを使ってグラフを作成します。

このグラフのノードは男女それぞれの番号で表されます。

辺には好意度に対応する重みが付いています。

import networkx as nx

# グラフを定義する
G = nx.Graph()
G.add_nodes_from(["F1", "F2", "F3", "F4", "F5"], bipartite=0)
G.add_nodes_from(["M1", "M2", "M3", "M4", "M5"], bipartite=1)
G.add_weighted_edges_from([
    ("F1", "M1", 70), ("F1", "M2", 90), ("F1", "M3", 80), ("F1", "M4", 80), ("F1", "M5", 70),
    ("F2", "M1", 60), ("F2", "M2", 10), ("F2", "M3", 80), ("F2", "M4", 70), ("F2", "M5", 60),
    ("F3", "M1", 70), ("F3", "M2", 70), ("F3", "M3", 100), ("F3", "M4", 70), ("F3", "M5", 60),
    ("F4", "M1", 80), ("F4", "M2", 80), ("F4", "M3", 80), ("F4", "M4", 50), ("F4", "M5", 60),
    ("F5", "M1", 90), ("F5", "M2", 90), ("F5", "M3", 90), ("F5", "M4", 90), ("F5", "M5", 30)
])

# 最大重みマッチングを求める
max_matching = nx.max_weight_matching(G)
print(max_matching)

NetworkXライブラリを用いて、与えられたグラフの最大重みマッチングを求めています。

---

まず、nx.Graph()を使って空のグラフを定義し、Gという変数に格納しています。

次に、add_nodes_fromを使って、グラフのノードを追加しています。

ここでは、[“F1”, “F2”, “F3”, “F4”, “F5”]と[“M1”, “M2”, “M3”, “M4”, “M5”]という2つの集合を作り、それぞれに対してbipartite=0とbipartite=1という属性を付与しています。

これによって、グラフが二部グラフであることを示しています。

---

その後、add_weighted_edges_fromを使って、グラフの辺を追加しています。

ここでは、各辺に対して、始点、終点、重みを設定しています。

最後に、nx.max_weight_matchingを使って、最大重みマッチングを求め、結果をmax_matchingに格納しています。

[実行結果]

{('F4', 'M1'), ('F1', 'M2'), ('M4', 'F5'), ('M3', 'F3'), ('F2', 'M5')}

最大重みマッチングによって、以上のような男女のペアを作ることができました。