BipartiteGraphMatching

クラス · 2 彩色済みの一般の無向グラフを二部マッチング本体（BipartiteMatching）に橋渡しするアダプタ

struct BipartiteGraphMatching;

概要

2 彩色済みの一般の無向グラフを二部マッチング本体（BipartiteMatching）に橋渡しするアダプタ

bipartite_coloring(g) の結果をそのまま渡して構築し、最大マッチング・最小頂点被覆・最大独立集合を元のグラフの頂点 id で取得する。 cpp auto color = bipartite_coloring(g); if (color) { BipartiteGraphMatching bgm(g, *color); auto mis = bgm.maximum_independent_set(); }

構築・破棄

名前	説明	計算量
`(constructor)`	2彩色済みの無向グラフからマッチングアダプタを構築する	$O(V+E)$

メンバ関数

名前	説明	計算量
`matching`	最大マッチングのサイズ	初回 $O(E\sqrt V)$、計算後は $O(1)$
`matching_pairs`	最大マッチングの辺集合（元の頂点 id の組）	$O(E\sqrt V+V)$
`minimum_vertex_cover`	最小頂点被覆（元の頂点 id、昇順）	$O(E\sqrt V+V)$
`maximum_independent_set`	最大独立集合（元の頂点 id、昇順）	$O(E\sqrt V+V)$

メンバの詳細

(constructor)

template <graph_type G>
BipartiteGraphMatching(const G &g, const std::vector<int> &color);

2彩色済みの無向グラフからマッチングアダプタを構築する

パラメータ g: 無向グラフ（list_graph<T> / csr_graph<T> のいずれでも可）
パラメータ color: 各頂点の色（0/1）。正当な 2 彩色であること。
計算量: $O(V+E)$