二部图

设 $G=<V,E>$ 为一个无向图, 若能将 $V$ 分为 $V_1$ 和 $V_2$, $V=V_1\cup V_2$, $\varnothing =V_1\cap V_2$, 使得 $G$ 中的每条边的两个顶点都是一个属于 $V_1$, 一个属于 $V_2$, 则称 $G$ 为二部图, $V_1,V_2$ 为互补顶点子集, $G$ 记作 $<V_1,V_2,E>$.

完全二部图

若 $G$ 是简单二部图, $V_1$ 中每个顶点均与 $V_2$ 中的所有顶点相邻, 则称 $G$ 为完全二部图, 记为 $K_{r,s}$, $r=|V_1|,s=|V_2|$.

指向原始笔记的链接

$n$ 阶零图为二部图.

定理 无向图 $G=<V,E>$ 是二部图当且仅当 $G$ 中无奇圈.