二部グラフ（自動色分け）

graph/bipartite_graph.hpp · GitHub で見る

共通ページ

無向グラフの隣接リスト vector<vector<int>> を渡し、二部判定・色分け・最大マッチング・最大独立集合・最小頂点被覆を求めます。左右の頂点番号を付け直す必要はなく、結果はすべて元の頂点番号です。

#include "lib/graph/bipartite_graph.hpp"

int main() {
	std::vector<std::vector<int>> g(5);
	for (auto [u, v] : std::vector<std::pair<int, int>>{ {0, 1}, {1, 2}, {2, 3}, {3, 0} }) {
		g[u].push_back(v);
		g[v].push_back(u);
	}
	BipartiteGraph graph(g);
	if (!graph.is_bipartite()) return 0;
	auto independent = graph.maximum_independent_set();
	auto cover = graph.minimum_vertex_cover();
	auto matching = graph.maximum_matching();
	assert(independent.size() == 3);
	assert(cover.size() == 2 && matching.size() == 2);
}

各無向辺は両端の隣接リストへ追加します。頂点番号は \([0,N)\)、頂点数は INT_MAX 未満、辺数は INT_MAX 以下です。非連結グラフ・孤立頂点・多重辺・空グラフに対応します。自己ループや奇数長の閉路があれば is_bipartite() は偽になります。

二部グラフでない場合、size()・empty()・is_bipartite()・再構築の build(g) を使えます。色分けや集合を取得する操作は、二部グラフであることを確認してから呼びます。入力を変更せず、構築後は入力を参照しません。

\(N\) を頂点数、\(M\) を無向辺数、\(K\) を色分け後の小さい側の頂点数とします。集合の取得時に必要なら最大マッチングを計算し、その結果を再利用します。下表の取得操作の計算量は、最大マッチングを計算済みの場合です。

操作	内容・返り値	計算量
BipartiteGraph(g)	無向隣接リストから構築し、二部判定・色分けを行う	\(O(N+M)\)
build(g)	指定したグラフで構築し直し、二部グラフなら真を返す	\(O(N+M)\)
size() / empty()	頂点数／頂点数が 0 か	\(O(1)\)
is_bipartite()	二部グラフか	\(O(1)\)
coloring()	各頂点の色 0 または 1 の const vector<int>&	\(O(1)\)
matching_size()	最大マッチングの辺数	\(O(1)\)
maximum_matching()	最大マッチングの頂点対 (色0,色1) の列	\(O(N)\)
mates()	各頂点の対応相手。未対応は -1	\(O(N)\)
minimum_vertex_cover()	全辺を少なくとも片端で覆う最小の頂点集合	\(O(N+M)\)
maximum_independent_set()	選んだ頂点間に辺がない最大の頂点集合	\(O(N+M)\)
minimum_edge_cover()	全頂点を覆う最小の頂点対の列。孤立頂点があれば nullopt	\(O(N+M)\)

最大独立集合の頂点数は \(N-\lvert\mathrm{matching}\rvert\)、最小頂点被覆の頂点数は最大マッチングの辺数です。両者は互いの補集合になります。最小辺被覆が存在する場合、その辺数も \(N-\lvert\mathrm{matching}\rvert\) です。空グラフの最小辺被覆は空の列です。

左右を指定して辺を追加したり、Hall 条件の反例・辺の分類を求めたりする場合は 二部マッチング を使います。このライブラリも同じマッチング処理を利用します。

構築は \(O(N+M)\)、最大マッチングの計算は \(K>0\) なら \(O((N+M)\sqrt K)\) 時間、\(K=0\) なら \(O(1)\) 時間です。保存領域は \(O(N+M)\)、集合の復元は \(O(N+M)\) 時間・追加空間です。

依存ライブラリ

• 二部マッチングの内部演算
• 二部マッチング

検証コード

• test/bipartite_graph.test.cpp

コード

#ifndef BIPARTITE_GRAPH_HPP
#define BIPARTITE_GRAPH_HPP

#include "bipartite_matching.hpp"
#include <cassert>
#include <cstddef>
#include <limits>
#include <optional>
#include <utility>
#include <vector>

class BipartiteGraph {
	bool bipartite_ = true;
	std::vector<int> color_, left_, right_;
	BipartiteMatching matching_{0, 0};
	std::vector<int> restore(BipartiteMatching::VertexSet vertices) const {
		std::vector<int> result;
		result.reserve(vertices.left.size() + vertices.right.size());
		for (int v : vertices.left) result.push_back(left_[v]);
		for (int v : vertices.right) result.push_back(right_[v]);
		return result;
	}

  public:
	BipartiteGraph() = default;
	explicit BipartiteGraph(const std::vector<std::vector<int>>& graph) { build(graph); }
	bool build(const std::vector<std::vector<int>>& graph) {
		assert(graph.size() < std::size_t(std::numeric_limits<int>::max()));
		int n = static_cast<int>(graph.size());
		bipartite_ = true;
		color_.assign(n, -1);
		left_.clear(), right_.clear();
		matching_ = BipartiteMatching(0, 0);
		std::vector<int> queue;
		queue.reserve(n);
		for (int root = 0; root < n; ++root) if (color_[root] < 0) {
			color_[root] = 0;
			queue.clear();
			queue.push_back(root);
			for (std::size_t head = 0; head < queue.size(); ++head) {
				int v = queue[head];
				for (int to : graph[v]) {
					assert(0 <= to && to < n);
					if (color_[to] < 0) color_[to] = color_[v] ^ 1, queue.push_back(to);
					else if (color_[to] == color_[v]) return bipartite_ = false;
				}
			}
		}
		std::vector<int> index(n);
		std::size_t m = 0;
		for (int v = 0; v < n; ++v) {
			auto& side = color_[v] ? right_ : left_;
			index[v] = static_cast<int>(side.size());
			side.push_back(v);
			if (!color_[v]) {
				assert(graph[v].size() <= std::size_t(std::numeric_limits<int>::max()) - m);
				m += graph[v].size();
			}
		}
		matching_ = BipartiteMatching(static_cast<int>(left_.size()), static_cast<int>(right_.size()));
		matching_.reserve(m);
		for (int v : left_) for (int to : graph[v]) matching_.add_edge(index[v], index[to]);
		return true;
	}
	int size() const { return static_cast<int>(color_.size()); }
	bool empty() const { return color_.empty(); }
	bool is_bipartite() const { return bipartite_; }
	const std::vector<int>& coloring() const { assert(bipartite_); return color_; }
	int matching_size() { assert(bipartite_); return matching_.build(); }
	std::vector<std::pair<int, int>> maximum_matching() {
		assert(bipartite_);
		auto result = matching_.edges();
		for (auto& [u, v] : result) u = left_[u], v = right_[v];
		return result;
	}
	std::vector<int> mates() {
		assert(bipartite_);
		std::vector<int> result(size(), -1);
		for (auto [u, v] : maximum_matching()) result[u] = v, result[v] = u;
		return result;
	}
	std::vector<int> minimum_vertex_cover() {
		assert(bipartite_);
		return restore(matching_.minimum_vertex_cover());
	}
	std::vector<int> maximum_independent_set() {
		assert(bipartite_);
		return restore(matching_.maximum_independent_set());
	}
	std::optional<std::vector<std::pair<int, int>>> minimum_edge_cover() {
		assert(bipartite_);
		auto ids = matching_.minimum_edge_cover();
		if (!ids) return std::nullopt;
		std::vector<std::pair<int, int>> result;
		result.reserve(ids->size());
		for (int id : *ids) {
			auto [u, v] = matching_.get_edge(id);
			result.emplace_back(left_[u], right_[v]);
		}
		return result;
	}
};

#endif

Back to top page