图论：二分图-基础

发表于 更新于 分类于 Artalk： loading...
二分图 匈牙利算法 最大匹配 DFS BFS实现

二分图经常用来研究两种不同类型对象之间的关系

关于二分图

主要参考二分图|维基百科 Wiki

定义

二分图的顶点可以分成两个互斥的独立点集 UU 和 VV ，使得所有的边都是由 UU 中一个顶点和 VV 中一个顶点构成的

Simple-bipartite-graph.svg

图片来自Wiki

特点

  • 二分图的每个集合内部，没有边相连

  • 二分图中的每个环都有偶数个顶点

一个图为二分图   ⟺  \iff 当且仅当图中不含有奇数环

奇数环：边数为奇数的环路

证明

「必要性」：⇒\Rightarrow

假设图中存在一个奇数环Circle-1，对其顶点进行编号，

graph LR
    A((1))---B((2))
    B---C((1))---D((2))---E((...))

起始点的编号一定是矛盾的。因为奇数次编号后，若开始是1，最后就成了2，开始是2，最后就是1，矛盾

「充分性」：⇐\Leftarrow

由于图中不存在奇数环，所以染色过程一定没有矛盾

一个图为二分图   ⟺  \iff 当且仅当图的着色数为2

如果图中没有环，例如：树，一定是二分图

染色法判定二分图

染色过程无矛盾，则可以判定为二分图

算法流程

1
2
3
4
5
遍历所有的顶点

    如果当前的顶点没有被染色

        DFS(i, color) // 深度优先搜索进行染色

代码实现

核心代码

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
/**
 * color[i] 有三种值
 * 0：没有染色
 * 1：染成1
 * 2：染成2
 **/
boolean dfs(int u, int c) {
    color[u] = c; // 当前顶点染色为c
    for (int i = h[u]; i != -1; i = ne[i]) { // 遍历所有相连的顶点
        int j = e[i];
        if (color[j] == 0) { 
            // 将相连顶点染成不同的色，并深搜
            if (!dfs(j, 3-c)) return false;
        }
        // 若相连顶点已经染色，但是和u相同颜色，则矛盾
        else if (color[j] == c) return false;
    }
    return true;
}

boolean flag = true;
for (int i = 1; i <= n; ++i) {
    if (color[i] == 0) {
        if (!dfs(i, 1)) {
            flag = false;
            break;
        }
    }
}
if (flag) log.write("Yes");
else log.write("No");

java版完整代码

acwing 860. 染色法判定二分图

给定一个 nn 个点 mm 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

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
import java.util.*;
import java.io.*;

class Main{
    static final int INF = 0x3f3f3f3f;
    static final int N = 100010;
    static final int M = 200010;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] color = new int[N];
    static int idx;
    static int n, m;
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    /**
     * color[i] 有三种值
     * 0：没有染色
     * 1：染成1
     * 2：染成2
     **/
    static boolean dfs(int u, int c) {
        color[u] = c; // 当前顶点染色为c
        for (int i = h[u]; i != -1; i = ne[i]) { // 遍历所有相连的顶点
            int j = e[i];
            if (color[j] == 0) { 
                // 将相连顶点染成不同的色，并深搜
                if (!dfs(j, 3-c)) return false;
            }
            // 若相连顶点已经染色，但是和u相同颜色，则矛盾
            else if (color[j] == c) return false;
        }
        return true;
    }
    public static void main(String[] args) throws Exception {
        String[] str = cin.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        Arrays.fill(h, -1);
        while (m-- > 0) {
            str = cin.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            add(a, b); add(b, a);
        }
        boolean flag = true;
        for (int i = 1; i <= n; ++i) {
            if (color[i] == 0) {
                if (!dfs(i, 1)) {
                    flag = false;
                    break;
                }
            }
        }
        if (flag) log.write("Yes");
        else log.write("No");
        
        
        log.flush();
        log.close();
        cin.close();
    }
}

二分图的最大匹配

相关基础概念

@Renfei Song

匹配

假定 GG 是一个二分图，由 GG 中一组没有公共顶点的边组成的集合 E′E' ，称作一个匹配

注意：

  1. 「匹配」首先是一个边的集合
  2. ∀ e1,e2∈E′,e1∩e2=∅\forall \ e_1, e_2 \in E', e_1 \cap e_2 =\empty

最大匹配

图 GG 所有匹配中，所含边数最多的匹配，称为最大匹配。

完美匹配

如果一个匹配中，包含了 GG 所有的顶点，则称之为完美匹配。

image-20220805221647067

图片来自Renfei Song

Fig.4 表示的匹配 Mperfect={E<1,7>,E<2,5>,E<3,6>,E<4,8>}M_{perfect}=\{E<1,7>,E<2,5>,E<3,6>,E<4,8>\} 就是个完美匹配

图 GG 中所有顶点都是 MperfectM_{perfect} 中的匹配点

显然，完美匹配一定是最大匹配，最大匹配不一定是完美匹配

匈牙利算法

原理分析

匈牙利算法，就是用来求解最大匹配问题的

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路

image-20220805224155738

图片来自Renfei Song

增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）

例如，Fig.5中的一条增广路如Fig.6所示（图中的匹配点均用红色标出）

image-20220805224237874

图片来自Renfei Song

增广路有一个重要特点：「非匹配边比匹配边多一条」

增广路中的匹配节点不存在其他相连的匹配边，因此交换匹配边和非匹配边的身份，不会破坏匹配的性质

交换后，图中的匹配边就比原来多了一条，达成改进匹配的目的

通过不停寻找增广路来增加匹配边，找不到增广路时，达到最大匹配(增广路定理)

这也是匈牙利算法的做法

可以将集合 UU 和集合 VV 中顶点匹配的过程视作，男女找对象的过程。

一个匹配集合，保证结成一对(匹配)的男生和女生，彼此只有对方一个对象(匹配集合中任意两条边都没有公共顶点)，禁止脚踏两只船

代码实现

核心代码，解析见注释

DFS

更适合稠密图

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
int res = 0; // 当前匹配的边数
for (int i = 1; i <= n1; ++i) {
    Arrays.fill(st, false); // 先置空状态
    if (find(i)) res++; // 匹配上，结果加一
}
//...
// 从男生视角出发
boolean find(int x) {
    // 为每一位男生找对象
    for (int i = h[x]; i != -1; i= ne[i]) {
        int j = e[i]; // 表示当前彼此有心意的女生。相连的顶点
        if (!st[j]) { // 如果当前女生没有被考虑过。该顶点不在交替路中
            st[j] = true; //考虑该女生。加入交替路
            // 如果该女生没有匹配的男朋友 或者 已经匹配上的男朋友，可以再找个新的女友，那就踹掉该女生(为了整体的利益分配最优)-_-!
            // 翻译过来
            // 如果该顶点是未匹配点，就直接匹配成功
            // 或者已经是匹配点，但是在路径上仍然可以找到一个未匹配点，也就是说这条路径是「增广路」，则交换路径上顶点的身份，增加匹配边
            if (match[j] == 0 || find(match[j])) {
                match[j] = x; // 该女生匹配上当前男生x
                return true;
            }
        }
    }
    return false;
}

最坏时间复杂度 O(nm)\Omicron(nm)

java版本完整代码

acwing 861. 二分图的最大匹配

image-20220805234938826
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
import java.util.*;
import java.io.*;

class Main{
    static final int INF = 0x3f3f3f3f;
    static final int N = 1010;
    static final int M = 100010;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] match = new int[N];
    static int idx;
    static boolean[] st = new boolean[N];
    static int n1, n2, m;
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    public static void main(String[] args) throws Exception {
        String[] str = cin.readLine().split(" ");
        n1 = Integer.parseInt(str[0]);
        n2 = Integer.parseInt(str[1]);
        m = Integer.parseInt(str[2]);
        int a, b;
        Arrays.fill(h, -1);
        while (m-- > 0) {
            str = cin.readLine().split(" ");
            a = Integer.parseInt(str[0]);
            b = Integer.parseInt(str[1]);
            add(a, b);
        }
        
        int res = 0; // 当前匹配的数量
        for (int i = 1; i <= n1; ++i) {
            Arrays.fill(st, false); // 先置空状态
            if (find(i)) res++;
        }
        log.write(String.valueOf(res));
        
        log.flush();
        log.close();
        cin.close();
    }
    
    static boolean find(int x) {
        for (int i = h[x]; i != -1; i= ne[i]) {
            int j = e[i];
            if (!st[j]) {
                st[j] = true;
                if (match[j] == 0 || find(match[j])) {
                    match[j] = x;
                    return true;
                }
            }
        }
        return false;
    }
}

补充

匈牙利算法还被用来解决「最小点覆盖」问题

存在一个点集 VminV_{min} ，二分图中所有的边都至少有一个端点 ∈Vmin\isin V_{min} ，即 VminV_{min} 覆盖到了二分图的所有边

关于如何求 VminV_{min} 中的点个数？

有一个 König 定理，1913年由匈牙利数学家柯尼希（D.Konig）提出，大致意思是：

『一个二分图的最大匹配数等于最小点覆盖个数』

证明略。暂时不会，待以后补充

参考资料