二部グラフの最大マッチング、最小点被覆、最大安定集合、最小辺被覆は相互のあいだに密接な関係があります。
グラフ上の最適化問題として有名なものとして、最大マッチング問題、最小点被覆問題、最大安定集合問題、最小辺被覆問題があります。これらはそれぞれ以下のようなものです。
最大マッチング問題と最大マッチングの求め方
辺からなる集合のうち、どの 2 辺も端点を共有しないようなものをマッチングと呼びます。そして最大サイズのマッチングを求める問題が最大マッチング問題です。下図のグラフでは赤太線で示した 2 本の辺集合が最大マッチングの一例になっています。
二部グラフの最大マッチングを求めるにはどうすればよいでしょうか？ 二部グラフなので白と黒の二色があれば隣り合う頂点を同じ色で塗らないように塗り分けることができます。
そしてふたつの超頂点 S と T を用意し、黒頂点から白頂点へ、超頂点 S から黒頂点へ、白頂点から超頂点 T へそれぞれ容量 1 の有向辺を張ったあと S から T へフローを流して最大流を求めれば最大マッチングを求めることができます。残余グラフの流量を調べれば具体的にどれとどれをマッチングさせればよいかもわかります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
/// 最大マッチングを求めるための MfGraph を構築する static (AtCoder.MfGraph<int> G, char[] LorR) BuildMatchingGraph(int n, List<(int, int)> E) { Dsu dsu = new Dsu(n * 2); foreach (var edge in E) { dsu.Merge(edge.Item1, edge.Item2 + n); dsu.Merge(edge.Item1 + n, edge.Item2); } for (int i = 0; i < n; i++) { if (dsu.Same(i, i + n)) throw new Exception("これは二部グラフではない！"); } int[][] groups = dsu.Groups(); char[] LorR = new char[n]; Array.Fill(LorR, '?'); foreach (int[] group in groups) { foreach (var v in group) { if (v < n && LorR[v] == '?') LorR[v] = 'L'; else if (v >= n && LorR[v - n] == '?') LorR[v - n] = 'R'; else break; } } AtCoder.MfGraph<int> G = new MfGraph<int>(n + 2); int s = n; int t = n + 1; foreach (var edge in E) { if (LorR[edge.Item1] == 'L') G.AddEdge(edge.Item1, edge.Item2, 1); if (LorR[edge.Item2] == 'L') G.AddEdge(edge.Item2, edge.Item1, 1); } for (int i = 0; i < n; i++) { if (LorR[i] == 'L') G.AddEdge(s, i, 1); if (LorR[i] == 'R') G.AddEdge(i, t, 1); } return (G, LorR); } /// 二部グラフの最大マッチングを求める public static List<(int, int)> MaximumMatching(int n, List<(int, int)> E) { (AtCoder.MfGraph<int> G, char[] LorR) res = BuildMatchingGraph(n, E); int s = n; int t = n + 1; AtCoder.MfGraph<int> G = res.G; int flow = G.Flow(s, t); List<(int, int)> matching = new List<(int, int)>(); foreach (var edge in G.Edges()) { if (edge.From == s || edge.To == t) continue; if (edge.Flow > 0) matching.Add((edge.From, edge.To)); } return matching; } |
最小点被覆問題と最小点被覆の求め方
頂点からなる集合のうち、それらの頂点から出ている辺をすべて集めるとすべての辺を覆うようなものを点被覆と呼びます。そして最小サイズの点被覆を求める問題が最小点被覆問題です。下図では赤丸で示した 3 頂点が最小点被覆の一例になっています。
最大マッチング問題や後述する最小辺被覆問題は一般のグラフでも多項式時間で解くことができますが、最小点被覆問題、最大安定集合問題は一般には NP困難 であることが知られています。しかし二部グラフであれば最小点被覆問題、最大安定集合問題も多項式時間で解くことができます。
二部グラフであれば最大マッチングから最小点被覆を求めることができます。この説明がわかりやすいです。
① 最大マッチングを求める。
② マッチング枝は右から左、それ以外は左から右へ向きをつける。
③ 左側の頂点でマッチング枝の端点でない頂点を赤く塗る。
④ 赤い頂点から矢印をたどって到達できる頂点を赤く塗る。
⑤ 左側の白い頂点、右側の赤い頂点が最小点被覆である。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
public static List<int> MinimumVertexCover(int n, List<(int, int)> E) { (AtCoder.MfGraph<int> G, char[] LorR) res = BuildMatchingGraph(n, E); int s = n; int t = n + 1; AtCoder.MfGraph<int> G = res.G; char[] LorR = res.LorR; int flow = G.Flow(s, t); List<int>[] G2 = new List<int>[n]; for (int i = 0; i < n; i++) G2[i] = new List<int>(); var edges = G.Edges(); bool[] matched_lefts = new bool[n]; foreach (var edge in edges) { if (edge.From == s || edge.To == t) continue; if (edge.Flow > 0) { G2[edge.To].Add(edge.From); matched_lefts[edge.From] = true; } if (edge.Flow == 0) { G2[edge.From].Add(edge.To); } } bool[] seen = new bool[n]; Queue<int> q = new Queue<int>(); for (int i = 0; i < n; i++) { if (LorR[i] == 'L' && !matched_lefts[i]) { q.Enqueue(i); seen[i] = true; } } while (q.Count > 0) { int cur = q.Dequeue(); foreach (var next in G2[cur]) { if (seen[next]) continue; seen[next] = true; q.Enqueue(next); } } List<int> minimumVertexCover = new List<int>(); for (int i = 0; i < n; i++) { if ((LorR[i] == 'L' && !seen[i]) || (LorR[i] == 'R' && seen[i])) minimumVertexCover.Add(i); } return minimumVertexCover; } |
最大安定集合問題と最大安定集合の求め方
頂点からなる集合のうち、どの 2 頂点も辺で結ばれていないようなものを安定集合と呼びます。最大サイズの安定集合を求める問題が最大安定集合問題です。下図では赤丸で示した 3 頂点が最大安定集合の一例になっています。
点被覆と安定集合とのあいだには以下のような関係があります。
一般の無向グラフにおいて、点被覆の補集合は安定集合をなし、安定集合の補集合は点被覆をなす。
二部グラフの最小点被覆を求め、それに含まれない頂点が最大安定集合になります。
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public static List<int> MaximumStableSet(int n, List<(int, int)> E) { HashSet<int> set = new HashSet<int>(MinimumVertexCover(n, E)); List<int> res = new List<int>(); for (int i = 0; i < n; i++) { if(!set.Contains(i)) res.Add(i); } return res; } |
最小辺被覆問題と最小辺被覆の求め方
辺からなる集合のうち、それらの辺の両端点をすべて集めるとすべての頂点を覆うようなものを辺被覆と呼びます。最小サイズの辺被覆を求める問題が最小辺被覆問題です。下図では赤太線で示した 4 辺が最小辺被覆の一例になっています。
最小辺被覆問題と最大マッチングとのあいだには以下のような関係があります。
孤立点のない一般の無向グラフでマッチングの端点となっていない頂点それぞれにつき 1 本ずつ枝を追加すると、それが最小辺被覆になる。
① 最大マッチングを求める。
② マッチング枝の端点でない頂点を赤く塗る。
③ 赤い頂点から辺を 1 本ずつ追加する。
④ 最大マッチング辺と ③ で追加した辺を合わせたものが最小辺被覆である。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
public static List<(int, int)> MinimumEdgeCover(int n, List<(int, int)> E) { (AtCoder.MfGraph<int> G, char[] LorR) res = BuildMatchingGraph(n, E); int s = n; int t = n + 1; AtCoder.MfGraph<int> G = res.G; char[] LorR = res.LorR; int flow = G.Flow(s, t); var edges = G.Edges(); bool[] matched = new bool[n]; List<(int, int)> minimumEdgeCover = new List<(int, int)>(); List<int>[] nexts = new List<int>[n]; for (int i = 0; i < n; i++) nexts[i] = new List<int>(); foreach (var edge in edges) { if (edge.From == s || edge.To == t) continue; if (edge.Flow > 0) { matched[edge.From] = true; matched[edge.To] = true; minimumEdgeCover.Add((edge.From, edge.To)); } else { nexts[edge.From].Add(edge.To); nexts[edge.To].Add(edge.From); } } for (int i = 0; i < n; i++) { if (!matched[i]) { if (nexts[i].Count == 0) throw new Exception("孤立点があります！"); minimumEdgeCover.Add((i, nexts[i][0])); } } return minimumEdgeCover; } |
G – Knight Placement
試しに問題を解いてみることにします。
問題の概要
縦 N 行、横 N 列のマス目がある。’.’ は空きマス、’#’ は壁マスであることを示す。
このマス目にコマを置けるだけ置きたい。コマの置き方には以下のような制約がある。
壁マスにコマを置くことはできない。
1 つのマスにコマを 2 つ以上置くことはできない。
マス (i, j) にコマが置かれているとき、マス (i ± A, j ± B)（複号任意）, マス (i ± B, j ± A)（複号任意）のどのマスにもコマを置くことはできない。この制約のもと置くことができるコマの個数の最大値を求め、コマの配置をひとつ出力せよ。
同時にコマを置くことができない 2 マスの間に辺を張ったグラフを考えると、このグラフの最大独立集合が求めるコマの配置です。
そしてこのグラフは二部グラフです。以下の方法で、同時にコマを置くことができない 2 マスをふたつの異なる色で塗り分けることができます。
A, B がどちらも奇数であるとき、i を 2 で割った余りによって マス (i, j) の色を決めればよい。
A, B の一方のみが奇数であるとき、i + j を 2 で割った余りによって マス (i, j) の色を決めればよい。
A, B が互いに素でないとき、最大公約数 g に対して (floor(i / g), floor(j / g)) が等しいようなマス (i, j) は同じ色で塗ることで、A, B が互いに素であるときの条件に帰着することができる。
同時にコマを置くことができない 2 マスの間に辺を張るとき、同じマスのあいだに何度も辺を張らないように注意が必要です。
辺を張ったら最大安定集合を取得しますが、安定集合に属する頂点であっても ‘.’ ではない頂点にはコマを置けないので除外します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
using AtCoder; class Program { static void Main() { int[] nab = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int A, int B) = (nab[0], nab[1], nab[2]); char[,] grid = new char[N, N]; for (int r = 0; r < N; r++) { char[] vs = Console.ReadLine().ToArray(); for (int c = 0; c < N; c++) grid[r, c] = vs[c]; } // 同時にコマを置くことができない 2 マスの間に辺を張るが、 // 同じマスのあいだに何度も辺を張らないように注意する List<(int, int)> E = new List<(int, int)>(); HashSet<string> set = new HashSet<string>(); (int, int)[] diffs = [(1, 1), (1, -1), (-1, -1), (-1, 1)]; for (int r = 0; r < N; r++) { for (int c = 0; c < N; c++) { if (grid[r, c] == '.') { bool find = false; // [r, c] -> [r ± A, c ± B] for (int i = 0; i < 4; i++) { int nr = r + A * diffs[i].Item1; int nc = c + B * diffs[i].Item2; if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue; if (grid[nr, nc] == '.') { find = true; int min = Math.Min(r * N + c, nr * N + nc); int max = Math.Max(r * N + c, nr * N + nc); string key = $"{min},{max}"; if (!set.Contains(key)) { set.Add(key); E.Add((min, max)); } } } // [r, c] -> [r ± B, c ± A] for (int i = 0; i < 4; i++) { int nr = r + B * diffs[i].Item1; int nc = c + A * diffs[i].Item2; if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue; if (grid[nr, nc] == '.') { find = true; int min = Math.Min(r * N + c, nr * N + nc); int max = Math.Max(r * N + c, nr * N + nc); string key = $"{min},{max}"; if (!set.Contains(key)) { set.Add(key); E.Add((min, max)); } } } } } } // 辺を張ったら最大安定集合を取得する List<int> res = MaximumStableSet(N * N, E); // 安定集合に属する頂点でも '.' でない頂点は除外する foreach (int v in res) { if (grid[v / N, v % N] == '.') grid[v / N, v % N] = 'o'; } for (int r = 0; r < N; r++) { char[] vs = new char[N]; for (int c = 0; c < N; c++) vs[c] = grid[r, c]; Console.WriteLine(new string(vs)); } } } |
