理解无向图二分图：掌握图论特殊结构的精髓

# 1. 无向图与二分图的基本概念

**1.1 无向图**

无向图是由一组顶点和一组无向边组成的数学结构。无向边连接顶点对，表示顶点之间的关系或交互。无向图中，边没有方向，因此两个顶点之间的边可以从任一顶点指向另一个顶点。

**1.2 二分图**

二分图是一种特殊的无向图，它可以被划分为两个不相交的顶点集合 V1 和 V2，使得图中的所有边都连接 V1 中的顶点和 V2 中的顶点。换句话说，二分图中不存在 V1 中顶点之间的边，也不存在 V2 中顶点之间的边。

# 2.1 二分图的定义和性质

**定义**

二分图是一种特殊的无向图，其顶点可以划分为两个不相交的集合 U 和 V，并且图中的每条边都连接一个 U 中的顶点和一个 V 中的顶点。换句话说，二分图的边集可以表示为 {(u, v) | u ∈ U, v ∈ V}。

**性质**

二分图具有以下性质：

* **独立集：**U 和 V 是图的两个最大独立集。
* **完美匹配：**如果 |U| = |V|，则存在一个匹配将 U 中的每个顶点与 V 中的一个顶点配对。
* **最大匹配：**对于任何二分图，总存在一个最大匹配，其中匹配的边数最多。
* **最小点覆盖：**对于任何二分图，总存在一个最小点覆盖，其中覆盖图中所有边的顶点数最少。

**定理**

**König定理：**对于一个二分图，其最大匹配的大小等于其最小点覆盖的大小。

**推论**

König定理表明，在二分图中，找到最大匹配等价于找到最小点覆盖。

**代码示例**

以下 Python 代码展示了如何创建和表示一个二分图：

from collections import defaultdict

class BipartiteGraph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

**逻辑分析**

该代码定义了一个 `BipartiteGraph` 类，其中 `graph` 字典存储了二分图的邻接表表示。`add_edge` 方法将一条边添加到图中，并确保两个顶点都包含在字典中。

# 3. 二分图的实际应用

### 3.1 二分图在任务分配中的应用

二分图在任务分配问题中有着广泛的应用。任务分配问题是指将一组任务分配给一组人员，使得每个任务都由一个人完成，并且每个人都分配到恰当数量的任务。

**二分图建模：**

我们可以将任务分配问题建模为一个二分图。其中，一