Graph Theory: Bipartite Graphs

二分图

简介

Undirected graph of vertices can be divided into two set of intersection is emptyX和Y,对于图中的每条边,One of the endpoints inX中,Another endpoint inY中,且X和YThere is no edge between internal vertex.

集合X和YHas one and only between each pair of vertices in the edge of a graph is called complete binary chart,可以记作$K_{n,m}$,n和m分别为X和Y集合中的顶点个数.

判定方法

染色法：

Each time you select a vertex is not dyedx,The first dye is yellow,接着从xDivision to dodfs遍历x所在的连通块.

在dfs的过程中,If now enumerated are at the edgeu→v,如果v还没有被染色,则把v染成和u不同的颜色,否则如果u和v颜色相同,Then the figure is not binary chart.

If the figure can be smoothly traversal by all connected in the block,Is this the graph is binary chart.

vector<int> edge[N];
int n, m, c[N];
//染色
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;
}

二分图最大匹配

简介

将二分图G=<V,E>的顶点集V拆分为$V_1$,$V_2$,$|V_1|\le |V_2|$,Choose some sideE’⊆E;

如果E’In any two side have the same vertex,则称E’为G的匹配;

G中边数最多的匹配称为G的最大匹配,Contains the number of edges is calledG的匹配数;

如果GThe maximum matching contains the number of edges of$=|V_1|$,Is called the match to complete match.

A set of maximum matching,Is also a complete match.

交错路径：如果P是G中的一条路径,并且对于POn the edge of each pair of adjacent（The endpoint contains the same vertex）,All meet the one in the matchM中,And another is not.

增广路径：A zigzag path in the path of the starting point and end point is not matching path called augmented path.

If we can find augmented pathP,那么M⊕P（对于一条边,如果它在M中出现不在PIn orP中出现不在M中出现）Is a set of better matching.

判定（匈牙利算法）

By constantly looking for new augmented road,To optimize the existing match.

时间复杂度：$O(nm)$

vector<int> edge[N];
int n, m, n1, n2, v[N];
bool b[N];
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;
    memset(v, 0, sizeof v);
    for (int i = 1; i <= n1; i++)
    {
        memset(b, false, sizeof b);
        if (find(i))
            ++ans;
    }
    return ans;
}

最大独立集

在图中选出最多的点,Meet them there is no boundary between two connected

$最大独立集=n-最大匹配数$

最小点覆盖

Choose the least point binary chart of each contains at least one of the two points on the side of.

$最小点覆盖=最大匹配数$

Board transfer binary chart

vector<int> edge[N];
int n, m, n1, n2;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
int a[N][N]; //Cannot be placed in the board points
int r[N][N]; //存储棋盘（二分图）The serial number of left and right sides point in

scanf("%d%d", &n, &m); // n*n的棋盘,有mNot placed the point
memset(a, 0, sizeof a);
n1 = n2 = 0;
for (int i = 1; i <= m; i++)
{
    int x, y;
    scanf("%d%d", &x, &y);
    a[x][y] = 1;
}
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (!a[i][j])
            if ((i + j) & 1)
                r[i][j] = ++n2;
            else
                r[i][j] = ++n1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (!a[i][j] && !((i + j) & 1))
            for (int k = 0; k < 4; k++)
            {
                int x = i + dx[k], y = j + dy[k];
                if (x < 1 || x > n || y < 1 || y > n || a[x][y])
                    continue;
                edge[r[i][j]].push_back(r[x][y]);
            }

Is transformed into binary chart question（拆点）

Will be in one point into a point and a point to get out,See if can hold for matching problem.