Edmonsのブロッサムアルゴリズムの概要とアルゴリズム及び実装例

Edmonsのブロッサムアルゴリズムの概要

Edmondsのブロッサムアルゴリズム（Edmonds’ Blossom Algorithm）は、一般グラフ（非二部グラフも含む）において最大マッチングを求めることを目的としたアルゴリズムで、二部グラフに限定されず、より広範なグラフ構造に対して適用できるため、社会ネットワーク、スケジューリング、構造解析など多様な分野で活用されている。

アルゴリズム名の「ブロッサム（blossom）」は、奇数長のサイクル（特に、オーグメンティングパス＝増加路の探索を妨げる構造）を指す。この奇数サイクルは、マッチングの拡張を阻害する要因となるため、アルゴリズムではこれを一時的に1つの「仮想頂点」として縮約（contract）し、探索を継続する戦略を取る。

この縮約・展開の処理により、一般グラフにおいても増加路の検出が可能となり、最大マッチングを正しく導出できるようになる。これは、ブロッサムアルゴリズムの核心的なアイデアであり、その名称の由来にもなっている。

ブロッサムアルゴリズムは、増加路（augmenting path）を逐次探索し、それを利用してマッチングを1本ずつ増やしていく方式に基づいており、増加路とは、未マッチの辺とマッチ済みの辺が交互に現れるような道で、端点が未マッチのノードである必要があるものとなる。

一般グラフでは、探索の途中で奇数長のサイクル（ブロッサム）が現れ、増加路の発見を妨げることがある。ブロッサムアルゴリズムではこの問題を解決するために、奇数サイクルを一時的に1つの「仮想頂点」として縮約（contract）し、探索を継続する。そして、増加路の発見・拡張後に、縮約されたブロッサムを再び展開してマッチングを正しく復元する。

手順の流れ

1. 初期化: 空のマッチング、または部分的なマッチングから開始する。

2. 増加路の探索: 未マッチの頂点を起点に、未マッチの辺とマッチ済みの辺を交互にたどる形で探索する。

3. ブロッサムの検出と縮約: 探索中に奇数長サイクル（ブロッサム）を発見した場合、そのサイクルを1つの頂点に見立てて縮約する。

4. マッチングの拡張: 増加路が見つかった場合、その道に沿ってマッチングを反転させ、1本マッチングを増やす。

5. 探索継続 or 完了判定: 増加路がこれ以上見つからない場合、最大マッチングが得られたと判断して終了する。

6. ブロッサムの展開とマッチング復元: 最後に、縮約されたブロッサムを元の構造に展開し、内部のマッチング状態を適切に復元する。

このように、ブロッサムアルゴリズムは「縮約→探索→拡張→展開」という手順を繰り返すことで、一般グラフにおいても正確な最大マッチングの構築**を可能にしている。

ブロッサムアルゴリズムの古典的なバージョン（Edmonds による1965年の原典実装）は、
時間計算量 O(V³) で動作する。これは、探索・縮約・展開といった操作を繰り返す中で、最悪の場合に多くのノード間操作が発生するためである。

その後、多くの研究によって改良が加えられ、特に Gabow や Micali-Vazirani らによる発展的アルゴリズムでは、O(√V × E) に近い計算時間で最大マッチングを求めることが可能になっている。これにより、より大規模なグラフにも適用できる現実的な計算性能が実現されている。

関連するアルゴリズム

以下に、Edmondsのブロッサムアルゴリズム関連性の高いアルゴリズムをカテゴリ別に述べる。

1. 最大マッチング系アルゴリズム（直接的に関連）

最大マッチング系アルゴリズムは、グラフにおける最大のマッチング（互いに辺を共有しないペアの集合）を効率的に求める手法群で、対象とするグラフの種類（二部か一般か）や目的（サイズ最大化かコスト最小化）に応じて、さまざまなアルゴリズムが提案されている。

2. 最大フローとマッチングの関係アルゴリズム

最大フローと最大マッチングは密接に関連しており、特に二部グラフではマッチング問題をフロー問題として解くことが可能となる。この関係を利用して、フローアルゴリズムを応用することで、効率的なマッチング解法が構築されている。

3. 関連する最適化アルゴリズム

最大マッチングと関連する最適化アルゴリズムは、割当問題や安定結婚問題、重み付きマッチングなど、マッチングの応用的側面を扱う。これらのアルゴリズムは、コスト・安定性・重みといった制約や目的に応じた最適なペアリングを実現するために設計されている。

4. 応用と研究ベースの関連技術

最大マッチングの応用は多岐にわたり、コンパイラ最適化や化学構造解析、コンピュータビジョン、オペレーションズリサーチなどの分野で重要な役割を果たしている。これらの分野では、グラフ構造を活用して効率的な対応付けや資源配分を実現している。

応用実装例

ここでは、Edmondsのブロッサムアルゴリズムの応用実装例として、ここでは次のような実世界のシナリオを用いた実装例について述べる。

応用シナリオ：人とプロジェクトのマッチング（一般グラフ）

問題設定：

• 各人が複数のプロジェクトに応募でき、またプロジェクト同士が競合している。

• プロジェクトAはBと競合しているが、Bに入ってもCには入れる、など非二部構造の相互関係がある。

• 「最大数の非競合な人・プロジェクトのペア」を選出する必要がある。

解法：

• このような非二部関係がある場合は、一般グラフとしてモデル化し、

• Edmondsのブロッサムアルゴリズムを使って最大マッチングを求める。

Python 実装（ライブラリ使用）

Pythonでは networkx ライブラリが Edmondsのブロッサム法による最大マッチング を実装済み。

import networkx as nx

# 一般グラフの作成
G = nx.Graph()

# ノード（人とプロジェクト）
nodes = ['Alice', 'Bob', 'ProjA', 'ProjB', 'ProjC']
G.add_nodes_from(nodes)

# エッジ（応募または関係があるペア）
edges = [
    ('Alice', 'ProjA'),
    ('Alice', 'ProjB'),
    ('Bob', 'ProjA'),
    ('Bob', 'ProjC'),
    ('ProjA', 'ProjB'),  # プロジェクト同士の競合
]
G.add_edges_from(edges)

# 最大マッチングの計算（Edmondsのアルゴリズム）
matching = nx.algorithms.matching.max_weight_matching(G, maxcardinality=True)

# 結果表示
print("最大マッチング:")
for u, v in matching:
    print(f"{u} — {v}")

出力例：

最大マッチング:
Alice — ProjB
Bob — ProjC

説明：

• プロジェクトAとBは競合しているが、ブロッサム法はA–Bの競合を扱える。

• BobがProjC、AliceがProjBに割り当てられた → 最大2ペアのマッチング

応用例リスト

ブロッサムアルゴリズムは、奇数長サイクル（ブロッサム）の検出・縮約・展開という特殊な処理が必要であり、これらのロジックが非常に複雑となる。そのため、正確に実装することは容易ではなく、アルゴリズム全体の構造も複雑になりがちである。

この実装の難しさから、多くの競技プログラミングやアルゴリズム学習の場では、まずは二部グラフに限定された最大マッチングアルゴリズム（例：Hopcroft-Karp法）を先に習得することが推奨されている。Hopcroft-Karpは構造が比較的単純で、効率的に動作するため、基礎的なマッチング理解の第一歩として適している。

具体的な適用事例