二分图

二分图

二分图：若能将无向图G=(V,E)的顶点V划分为两个交集为空的顶点集，并且任意边的两个端点都分属于两个集合，则称图G为一个为二分图。

完全二分图

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

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

二分图判定

c[i]代表每个点涂的颜色，涂色为1或2，通过判断颜色是否冲突来判断二分图

vector<int> edge[N + 1];
int n, m, c[N + 1];
bool dfs(int x) {//染色
    for (auto y : edge[x]) {
        if (!c[y]) {
            c[y] = 3 - c[x];
            if (!dfs(y)) return false;
        }
        else if (c[x] == c[y]) return false;
    }
    return true;
}
​
bool check() {
    memset(c, 0, sizeof(c));
    for (int i = 1; i <= n; i++) {
        if (!c[i]) {
            c[i] = 1;
            if (!dfs(i)) return false;
        }
    }
    return true;
}
​
void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    if (check()) printf("Yes\n");
    else printf("No\n");
}

二分图匹配

概念

由增广路的性质，增广路中的匹配边总是比未匹配边多一条，所以如果我们放弃一条增广路中的匹配边，选取未匹配边作为匹配边，则匹配的数量就会增加。匈牙利算法就是在不断寻找增广路，如果找不到增广路，就说明达到了最大匹配。匈牙利算法（二分图）博客园

vector<int>edge[N + 1];
int n, m, n1, n2, v[N + 1];//v[i]记录匹配情况
bool b[N + 1];
bool find(int x) {
    b[x] = true;
    for (auto y : edge[x]) {
        if (!v[y] || (!b[v[y]] && find(v[y]))) {
            v[y] = x;
            return true;
        }
    }
    return false;
}
int match() {
    int ans = 0;
    for (int i = 1; i <= n1; i++) {
        memset(b, false, sizeof(b));
        if (find(i)) ans++;
    }
    return ans;
}

棋盘覆盖问题：

将棋盘涂成黑白交错的颜色，进行二分图匹配，黑向白连边

最大独立集

最大独立集是指：在图中选出最多的点，满足他们两两之间没有边相连

最大独立集等于总点数-最大匹配数

注意如何建立二分图

二分图最小点覆盖：选择最少的路径，使得每条边至少有一个点被选中；

最小点覆盖等于等于总点数-边的最大匹配数

注意二分图的拆分方式