最后更新: 2025-01-22 09:22 查看: 42 次反馈刷题

二分图

定义8．23（二分图）若图 $G$ 的顶点集 $V$ 能划分为两个子集 $V_1$ 和 $V_2$ ，并且每条边的一个端点在 $V_1$ 中，另一个端点在 $V_2$ 中，则称 $G$ 为二分图，记为 $G\left(V_1, V_2\right)$ 。 $V$ 划分为 $V_1$ 和 $V_2$ ，称为 $G$ 的一个二划分。记为 $\left(V_1, V_2\right)$ 。若简单图 $G$ 具有二划分 $\left(V_1, V_2\right)$ ，并且 $V_1$ 中每个顶点与 $V_2$ 中每个顶点恰有一条边相连，称 $G$ 为完全二分图。若 $\left|V_1\right|=m,\left|V_2\right|=n$ ，则这样的完全二分图记为 $K_{m, n}$ 。例如，图 8.10 给出完全二分图记为 $K_{3,3}$ 。
利用回路的概念，可以给出二分图的性质。
 ![图片](/uploads/2025-01/5a0a98.jpg)
 
 利用回路的概念，可以给出二分图的性质。
定理8．13 $G$ 是二分图当且仅当 $G$ 中没有奇回路。
证明：$\Rightarrow$ 设 $G$ 是具有二划分 $\left(V_1, V_2\right)$ 的二分图，并且 $G$ 具有一条回路 $C$ ：$\left(v_0\right.$ ， $v_1, \cdots, v_m, v_0$ ）。不失一般性，设 $v_0 \in V_1$ ，因为 $\left\{v_0, v_1\right\} \in E$ ，且 $G$ 是二分图，所

图 8.10以 $v_1 \in V_2$ ，同理 $v_2 \in V_1$ 。则可以推导出 $v_{2 i} \in V_1, v_{2 i+1} \in V_2$ 。因为 $v_0 \in V_1$ ，所以 $v_m \in V_2$ 。

因而存在 $k$ 使 $m=2 k+1$ ，即回路 $C$ 是偶回路。
$\Leftarrow: ~$ 设 $G$ 是连通图，否则对 $G$ 的每个分支进行证明。又设 $G$ 中没有奇回路。任取一个顶点 $u \in V$ ，且令 $V_1=\{x \mid$ 从 $u$ 到 $x$ 有一条偶路 $\}, V_2=\{y \mid$ 从 $u$ 到 $y$ 有一条奇路 $\}$ 。下面证明 $\left(V_1, V_2\right)$ 是 $G$ 的一个二划分。

因为 $G$ 是连通图，所以 $V_1 \cup V_2=V$ 。通过反证法证明 $V_1 \cap V_2=\varnothing$ 。假设存在一个顶点 $v \in V_1 \cap V_2$ ，则从 $u$ 到 $v$ 有一条偶路 $p_1$ 和一条奇路 $p_2$ ，所以 $G$ 中没有一条奇路，它的边集是 $p_1 \cup p_2$ 的子集（证明留作习题），与 $G$ 中没有奇回路矛盾。因此 $V_1 \cap V_2=\varnothing$ 。

再证明 $G$ 中每一边的一个端点在 $V_1$ 中，另一个端点在 $V_2$ 中，用反证法证明之。若有一边连接 $V_2$ 中的两个顶点 $y_1$ 和 $y_2$ ，即 $y_1 \in V_2, y_2 \in V_2$ 。因为从 $u$ 到 $y_1$ 有一条奇路，则必有一条从 $u$ 到 $y_2$ 的偶路，这与 $y_2 \in V_2$ 矛盾。所以任意一边的两个端点不能同在 $V_2$ 中。同理，任意一边的两个端点也不能同在 $V_1$ 中。

因此 $G\left(V_1, V_2\right)$ 是二分图。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：路径矩阵

下一篇：欧拉图和半欧拉图

本文对您是否有用？有用 (0) 无用 (0)