##### 二分图 - 二分图 - **二分图**指顶点集可分为两个互不相交的子集, 使得边只连接不同子集的顶点的[[图]]. 二分图是一个[[无向图]] $G=(V,E)$, 其中顶点集 $V$ 可以[[集合划分|划分]]为两个不相交的子集 $U$ 和 $W$, 即 $V=U\cup W$, $U\cap W=\emptyset$, 并且每条边 $e\in E$ 的一个端点属于 $U$, 另一个端点属于 $W$. 二分图涉及[[二分图的判定|判定]]和[[二分图的匹配|匹配]]问题 - $G=(V,E)$, $V=U\cup W$, $U\cap W=\emptyset$ - $\forall e=(u,w)\in E$, $u\in U$, $w\in W$