01.Graph-Bipartite-Basic.md

1.1 二分图的定义

二分图（Bipartite Graph）：一种特殊的图，其顶点集可以被划分为两个互不相交的子集，使得图中的每一条边都连接着这两个子集中的顶点。换句话说，二分图中的顶点可以被分成两组，使得同一组内的顶点之间没有边相连。

1.2 二分图的性质

1. 染色性质：二分图是二色的，即可以用两种颜色对顶点进行着色，使得相邻顶点颜色不同。
2. 无奇环：二分图中不存在长度为奇数的环。
3. 最大匹配：二分图的最大匹配问题可以通过匈牙利算法或网络流算法高效求解。

1.3 二分图的判定

判断一个图是否为二分图的方法：

1. 使用深度优先搜索（DFS）或广度优先搜索（BFS）进行二着色
2. 如果在染色过程中发现相邻顶点颜色相同，则该图不是二分图
3. 如果能够成功完成二着色，则该图是二分图

1.4 二分图的应用场景

1. 任务分配：将工人和任务分别作为两个顶点集，边表示工人可以完成的任务
2. 婚姻匹配：将男性和女性分别作为两个顶点集，边表示可能的配对关系
3. 网络流问题：许多网络流问题可以转化为二分图最大匹配问题
4. 资源分配：将资源和需求分别作为两个顶点集，边表示资源可以满足的需求

1.5 二分图的基本算法

1. 匈牙利算法：用于求解二分图的最大匹配
2. Hopcroft-Karp算法：用于求解二分图的最大匹配，时间复杂度更优
3. 网络流算法：将二分图最大匹配问题转化为最大流问题求解

1.6 二分图的判定代码

def is_bipartite(graph):
    """
    判断图是否为二分图
    :param graph: 邻接表表示的图
    :return: 是否为二分图
    """
    n = len(graph)
    colors = [0] * n  # 0表示未染色，1和-1表示两种不同的颜色
    
    def dfs(node, color):
        colors[node] = color
        for neighbor in graph[node]:
            if colors[neighbor] == color:
                return False
            if colors[neighbor] == 0 and not dfs(neighbor, -color):
                return False
        return True
    
    for i in range(n):
        if colors[i] == 0 and not dfs(i, 1):
            return False
    return True

1.7 常见问题类型

1. 判断图是否为二分图
2. 求二分图的最大匹配
3. 求二分图的最小点覆盖
4. 求二分图的最大独立集
5. 求二分图的最小路径覆盖

1.8 注意事项

1. 在实现二分图算法时，需要注意图的表示方式（邻接表或邻接矩阵）
2. 对于大规模图，需要考虑算法的空间复杂度
3. 在实际应用中，可能需要根据具体问题对基本算法进行优化
4. 处理有向图时，需要先将其转换为无向图再判断是否为二分图