二分グラフの基礎概念
- 基本的性質
- 二分グラフの判定方法
- マッチング問題
-
- ハンガリアン法
- KMアルゴリズム
- ハンガリアン法
- 点カバーと独立集合
-
- 最小点カバー問題
- 最大独立集合問題
- DAGの最小パス点カバー
- DAGの最小パス重複点カバー
- 最小点カバー問題
- Hallの定理
-
- HDU 6667 Roundgod and Milk Tea
- [ARC076F] Exhausted?
- CF981F Round Marriage
- [POI2009]LYZ-Ice Skates
- CF103E Buying Sets
- [ARC106E] Medals
- [AGC029F] Construction of a tree
- [AGC037D] Sorting a Grid
- [CERC2016] 二分毯 Bipartite Blanket
- HDU 6667 Roundgod and Milk Tea
基本的性質
グラフ G = (V, E) が与えられたとき、頂点集合 V を2つの空でない部分集合 VL, VR に分割でき、各部分集合内には辺が存在せず、部分集合間には辺が存在しうる場合、このグラフを二分グラフと呼びます。VL と VR をそれぞれ二分グラフの左部、右部と称します。
二分グラフの判定
グラフに奇数長のサイクルが存在する場合、そのグラフは二分グラフではありません。逆に、奇数長のサイクルが存在しない場合、グラフは必ず二分グラフとなります。この性質を利用して、頂点を彩色することで奇数長のサイクルの存在を検出できます。
実装例：
bool dfsCheck(int vertex, int color, vector<int>& colors, const vector<vector<int>>& graph) {
colors[vertex] = color;
for (int neighbor : graph[vertex]) {
if (colors[neighbor] == -1) {
if (!dfsCheck(neighbor, 3 - color, colors, graph)) {
return false;
}
} else if (colors[neighbor] == colors[vertex]) {
return false; // 隣接頂点が同じ色
}
}
return true;
}
マッチング問題
二分グラフ G = (V, E) において、辺集合 E' の中の任意の2辺が共通の端点を持たない場合、E' をマッチングと呼びます。最大の E' のサイズを持つマッチングを最大マッチングと呼びます。左部と右部の頂点数が等しく、最大マッチングのサイズも同じ場合、これを完全マッチングと呼びます。辺に重みがある場合、最大マッチングの中で重みの合計が最大のものを重み付き最大マッチングと呼びます。
ハンガリアン法
マッチングにおいて、一致しない2頂点を結ぶ経路で、一致辺と非一致辺が交互に出現するものを増加路と呼びます。増加路上のすべての辺の状態を反転させると、より大きなマッチングが得られます。
実装例：
bool tryMatch(int leftNode, vector<bool>& visited, vector<int>& matchRight, const vector<vector<int>>& graph) {
for (int rightNode : graph[leftNode]) {
if (!visited[rightNode]) {
visited[rightNode] = true;
if (matchRight[rightNode] == -1 || tryMatch(matchRight[rightNode], visited, matchRight, graph)) {
matchRight[rightNode] = leftNode;
return true;
}
}
}
return false;
}
int findMaxMatching(const vector<vector<int>>& graph, int leftSize, int rightSize) {
vector<int> matchRight(rightSize, -1);
int result = 0;
for (int i = 0; i < leftSize; i++) {
vector<bool> visited(rightSize, false);
if (tryMatch(i, visited, matchRight, graph)) {
result++;
}
}
return result;
}
KMアルゴリズム
KMアルゴリズムは重み付き最大マッチングを解くためのアルゴリズムです。ただし、完全マッチングが存在することを前提とします。
各左部頂点に値 Ai、各右部頂点に値 Bj を割り当て、∀i,j において Ai + Bj ≥ w(i,j) を満たすようにします。これらの値を頂点ラベルと呼びます。Ai + Bj = w(i,j) を満たす辺だけで構成される部分グラフを等値部分グラフと呼びます。
実装例：
bool kmDFS(int leftNode, vector<bool>& leftVisited, vector<bool>& rightVisited,
vector<int>& leftLabel, vector<int>& rightLabel,
vector<int>& matchRight, vector<int>& slack, const vector<vector<int>>& weights, int n) {
leftVisited[leftNode] = true;
for (int rightNode = 0; rightNode < n; rightNode++) {
if (!rightVisited[rightNode]) {
int gap = leftLabel[leftNode] + rightLabel[rightNode] - weights[leftNode][rightNode];
if (gap == 0) {
rightVisited[rightNode] = true;
if (matchRight[rightNode] == -1 || kmDFS(matchRight[rightNode], leftVisited, rightVisited,
leftLabel, rightLabel, matchRight, slack, weights, n)) {
matchRight[rightNode] = leftNode;
return true;
}
} else if (gap < slack[rightNode]) {
slack[rightNode] = gap;
}
}
}
return false;
}
int solveKM(const vector<vector<int>>& weights, int n) {
vector<int> leftLabel(n, 0), rightLabel(n, 0);
vector<int> matchRight(n, -1);
for (int i = 0; i < n; i++) {
leftLabel[i] = *max_element(weights[i].begin(), weights[i].end());
}
for (int leftNode = 0; leftNode < n; leftNode++) {
vector<int> slack(n, INT_MAX);
vector<bool> leftVisited(n, false), rightVisited(n, false);
while (!kmDFS(leftNode, leftVisited, rightVisited, leftLabel, rightLabel, matchRight, slack, weights, n)) {
int delta = INT_MAX;
for (int j = 0; j < n; j++) {
if (!rightVisited[j] && slack[j] < delta) {
delta = slack[j];
}
}
for (int j = 0; j < n; j++) {
if (leftVisited[j]) leftLabel[j] -= delta;
if (rightVisited[j]) rightLabel[j] += delta;
else slack[j] -= delta;
}
}
}
int result = 0;
for (int j = 0; j < n; j++) {
if (matchRight[j] != -1) {
result += weights[matchRight[j]][j];
}
}
return result;
}
点カバーと独立集合
二分グラフにおいて、すべての辺の少なくとも一方の端点を含む頂点集合を点カバーと呼びます。頂点集合内の任意の2頂点間に辺がない場合、その集合を独立集合と呼びます。
最小点カバー
Königの定理により、二分グラフの最小点カバーのサイズは最大マッチングのサイズと等しくなります。
最大独立集合
最大独立集合のサイズは、全体の頂点数から最大マッチングのサイズを引いたものに等しくなります。
DAGの最小パス点カバー
DAGの最小パス点カバー問題は、グラフを二分グラフに変換することで解けます。結果のパス数は、頂点数から変換後の二分グラフの最大マッチングサイズを引いたものに等しくなります。
DAGの最小パス重複点カバー
頂点が複数のパスでカバーされることを許容する場合、まずグラフの推移的閉包を計算し、その後通常の最小パス点カバー問題を解きます。
Hallの定理
二分グラフの左部を VL、右部を VR とし、|VL| ≤ |VR| と仮定します。この二分グラフがサイズ |VL| のマッチングを持つための必要十分条件は、∀S ⊆ VL において |S| ≤ |∪v∈S N(v)| が成り立つことです。
HDU 6667 Roundgod and Milk Tea
この問題は二分グラフの最大マッチング問題ですが、直接計算すると計算量が大きくなります。Hallの定理の系を応用し、各クラスの制約を考慮して効率的に解きます。
実装例：
void solveProblem() {
long long totalA = 0, totalB = 0;
int n;
scanf("%d", &n);
vector<long long> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld", &a[i], &b[i]);
totalA += a[i];
totalB += b[i];
}
long long result = min(totalA, totalB);
for (int i = 1; i <= n; i++) {
result = min(result, totalA - a[i] + totalB - b[i]);
}
printf("%lld\n", result);
}
[ARC076F] Exhausted?
この問題は最大マッチングのサイズを求めるものですが、答えは n から最大マッチングサイズを引いたものになります。Hallの定理の系を用いて効率的に解くことができます。
CF981F Round Marriage
二分探索を用いて、距離の制約を満たすマッチングが存在するかを判定します。Hallの定理に基づき、制約条件を満たすかどうかを双ポインタで効率的に判定します。
[POI2009]LYZ-Ice Skates
Hallの定理を応用し、区間内の人数が靴の数を超えないという制約を管理します。セグメント木を用いて最大部分区間和を効率的に計算します。
CF103E Buying Sets
制約条件を満たすため、特別な重み付けを行ったネットワークフローを構築し、最小カットを求めることで問題を解決します。
[ARC106E] Medals
二分探索と高次元前処理和を組み合わせることで、制約条件を満たすかどうかを効率的に判定します。
[AGC029F] Construction of a tree
まず最大流を用いて解の存在を判定し、DFSを用いて実際の木構造を構築します。
[AGC037D] Sorting a Grid
列ごとにマッチング問題を解き、Hallの定理によって解の存在を保証しながらグリッドをソートします。
[CERC2016] 二分毯 Bipartite Blanket
二分グラフの性質と高次元前処理和を組み合わせることで、すべての部分集合について制約を満たすかどうかを効率的に判定します。