二部图

二部图

$G=⟨V,E⟩$ 为无向图，若 $V$ 可分为两个互不相交的子集 $V_1$ 和 $V_2$，使得 $E$ 中的每条边的两个端点分别属于 $V_1$ 和 $V_2$，则称 $G$ 为二部图（也称二分图 或 偶图）。
称 $V_1$ 和 $V_2$ 为 $G$ 的互补顶点子集。
常将二部图记作 $G=⟨V_1,V_2,E⟩$。

完全二部图

$\mathrm{\forall }{v}_1\in V_1,v_2\in V_2$，$(v_1,v_2)\in E$，则称 $G$ 为完全二部图。 记为 $K_{r,s}$，其中 $r=|V_1|$，$s=|V_2|$。

二部图的判定

$G$ 为二部图当且仅当 $G$ 中不含奇圈。