【图论笔记】图论基础（3）：二部图和完全图

1. 二部图

设 $S$ 是一个集合， $S_1,S_2,\dots,S_t$ 是 $S$ 的子集．如果
1. $S_1,S_2,\dots,S_t$ 都不是空集；
2. $S=S_1\cup S_2\cup \dots S_t$ ；
则称 $S_1,S_2,\dots,S_t$ 是 $S$ 的一个划分．

设 $G$ 是一个图．如果 $V(G)$ 可以划分为两个集合 $X$ 和 $Y$ ，使得对每一个边总有一个端点落入 $X$ ，一个端点落入 $Y$ ，那么我们就说图 $G$ 是一个二部图，记作 $G[X,Y]$ ，并且称划分 $X,Y$ 是 $G$ 的一个二部划分， $X$ 和 $Y$ 是它的两个分部．

设 $G[X,Y]$ 是二部图，那么 $G[X]$ 与 $G[Y]$ 显然是空图，换言之， $G$ 的所有边都落在 $X$ 和 $Y$ 之间，而 $X$ 内部和 $Y$ 的内部都没有边．

长度为奇数的圈称为奇圈；长度为偶数的圈为偶圈．
设 $u,v$ 是图 $G$ 上两个顶点，连接 $u,v$ 的最短路的长度叫做 $u,v$ 之间的距离，记作 $dist(u,v)$ ．

性质1. 偶圈和路是二部图，奇圈不是二部图．

证明. （1）设 $P=v_1v_2\dots v_n$ 是一条路．令所有与 $v_1$ 的距离为偶数的顶点构成集合 $X$ ，所有与 $v_1$ 的距离为偶数的顶点构成集合 $Y$ ．那么 $X,Y$ 显然是 $V(P)$ 的一个划分，而且 $X=\{v_2,v_4,\dots\}$ ， $Y=\{v_1,v_3,\dots\}$ ，这显然是一个二部划分．

（2）设 $C=v_1v_2\dots v_{2k}$ 是一个偶圈．设 $P=G\setminus v_{2k}v_1$ ，显然 $P$ 是一条路．按（1）的方法可以将 $V(P)$ 划分为 $X,Y$ 使得 $X,Y$ 是 $P$ 的一个二部划分．按照（1）的方法， $X=\{v_2,v_4,\dots,x_{2k}\}$ ， $Y=\{v_1,v_3,\dots,v_{2k-1}\}$ ．再将边 $v_{2k}v_1$ 加回来，容易看出 $X,Y$ 也是 $C$ 的一个二部划分．

（3）设 $C=v_1v_2\dots v_{2k+1}$ 是一个奇圈．假设 $C$ 有二部划分 $X,Y$ ．不妨设 $v_1\in Y$ ，那么显然在 $C$ 上与 $v_1$ 的距离为偶数的顶点都落在 $Y$ 中，所有与 $v_1$ 距离为奇数的顶点都落在 $X$ 中．注意： $v_k$ 和 $v_{k+1}$ 与 $v_1$ 的距离都是 $k$ （ $v_1$ 到 $v_k$ 的最短路是 $v_1v_2\dots v_k$ ， $v_1$ 到 $v_{k+1}$ 的最短路是 $v_1v_{2k+1}v_{2k}\dots v_{k+1}$ ），所以 $v_k$ 与 $v_{k+1}$ 要么同时落入 $X$ 要么同时落入 $Y$ ，但 $v_kv_{k+1}\in E(C)$ ，矛盾． $\Box$

性质2. 图 $G$ 是二部图当且仅当 $G$ 没有奇圈．

证明. $(\Rightarrow)$ 设 $G$ 是二部图．假设 $G$ 有奇圈，那么由性质1可得 $G$ 不是二部图，矛盾．
$(\Leftarrow)$ 不妨设 $G$ 是连通图（否则取其连通分支），且非平凡．设 $G$ 没有奇圈．任取 $y\in V(G)$ ，设 $G$ 中所有与 $y$ 距离为偶数的顶点构成的集合为 $Y$ ，所有与 $y$ 距离为奇数的顶点构成的集合为 $X$ ．显然 $X,Y$ 是 $V(G)$ 的一个划分．以下只需证明： $X$ 中任意两顶点不连边， $Y$ 中任意两顶点也不连边．

任取 $X$ 中两个顶点 $x_1,x_2$ ，那么 $x_1$ 和 $y$ 之间存在长度为奇数的路 $P_1$ ， $x_2$ 和 $y$ 之间也存在长度为奇数的路 $P_2$ ．假设 $x_1x_2\in E(G)$ ，那么 $P_1$ ， $P_2$ 和边 $x_1x_2$ 构成一个奇数长的闭游走，奇数长的闭游走必然包含奇圈，矛盾．所以 $X$ 中任意两顶点不连边，同理 $Y$ 中任意两顶点不连边． $\Box$

推论3. 森林是二部图． $\Box$

2. 完全图

设 $G$ 是一个 $n$ 阶简单图．如果 $G$ 的任意两个顶点都相邻，那么 $G$ 叫做== $n$ 阶完全图==，简称完全图，记作 $K_n$ ．

性质4. $e(K_n)=\binom{n}{2}=\frac{n(n-1)}{2}.$

注意：任何 $n$ 阶简单图都可以看作是 $K_n$ 的子图．

设 $G$ 是 $n$ 阶简单图，设 $H$ 也是一个 $n$ 阶图，其顶点集为 $V(H)=V(G)$ ，其边集 $E(H)=E(K_n)\setminus E(G)$ ，则称 $H$ 是 $G$ 的补图． $G$ 的补图记作 $\overline{G}$ ．

3. 完全二部图

设 $G[X,Y]$ 是一个简单的二部图．如果对于任意 $x\in X$ 和任意 $y\in Y$ ， $x,y$ 总是相邻的，则称 $G[X,Y]$ 是完全二部图；特别地，如果 $|X|=m,~|Y|=n$ ，那么这个完全二部图记作 $K_{m,n}$ ．

$K_{1,t}$ 是一种特殊的树，称为 $t$ -星

性质5. $e(K_{m,n})=mn.$

返回【图论笔记】

【图论笔记】图论基础（3）：二部图和完全图

目录

1. 二部图

2. 完全图

3. 完全二部图