最大二部マッチング (maximum bipartite matching)
概要
最大二部マッチングは、二部グラフ \(G = (V, E)\) 上で各辺の容量が1の、最大マッチングを求める問題である。
二部グラフ上では、以下の関係が成り立つ
-
最大マッチング のサイズ + 最小辺被覆 のサイズ = \(|V|\)
-
最大マッチング のサイズ = 最小点被覆 のサイズ
-
最大安定集合 のサイズ + 最小点被覆 のサイズ = \(|V|\)
Hopcroft-Karp Algorithm
最大二部マッチングを解くアルゴリズムである。
Dinic’s Algorithmと同じで、以下の手順を繰り返して解を求める。
-
BFSでsourceから各頂点までの距離(\(level\))を計算
-
DFSで、sourceからの距離が遠くなるようなパスを見つけ、フローを流す
計算量
\(O(|E| \sqrt{|V|})\)
実装
# Hopcroft-Karp Algorithm
from collections import deque
class HopcroftKarp:
def __init__(self, N0, N1):
self.N0 = N0
self.N1 = N1
self.N = N = 2+N0+N1
self.G = [[] for i in range(N)]
for i in range(N0):
forward = [2+i, 1, None]
forward[2] = backward = [0, 0, forward]
self.G[0].append(forward)
self.G[2+i].append(backward)
self.backwards = bs = []
for i in range(N1):
forward = [1, 1, None]
forward[2] = backward = [2+N0+i, 0, forward]
bs.append(backward)
self.G[2+N0+i].append(forward)
self.G[1].append(backward)
def add_edge(self, fr, to):
#assert 0 <= fr < self.N0
#assert 0 <= to < self.N1
v0 = 2 + fr
v1 = 2 + self.N0 + to
forward = [v1, 1, None]
forward[2] = backward = [v0, 0, forward]
self.G[v0].append(forward)
self.G[v1].append(backward)
def bfs(self):
G = self.G
level = [None]*self.N
deq = deque([0])
level[0] = 0
while deq:
v = deq.popleft()
lv = level[v] + 1
for w, cap, _ in G[v]:
if cap and level[w] is None:
level[w] = lv
deq.append(w)
self.level = level
return level[1] is not None
def dfs(self, v, t):
if v == t:
return 1
level = self.level
for e in self.it[v]:
w, cap, rev = e
if cap and level[v] < level[w] and self.dfs(w, t):
e[1] = 0
rev[1] = 1
return 1
return 0
def flow(self):
flow = 0
G = self.G
bfs = self.bfs; dfs = self.dfs
while bfs():
*self.it, = map(iter, G)
while dfs(0, 1):
flow += 1
return flow
def matching(self):
return [cap for _, cap, _ in self.backwards]