二分图

概述

二分图（Bipartite Graph），也称为双部图，是一种特殊的图结构。在二分图中，图的顶点集可以分成两个不相交的子集 U 和 V ，并且图中的每条边都连接一个属于 U 的顶点和一个属于 V 的顶点。

换句话说，没有任何一条边会连接同一个子集内的两个顶点。

定义

一个图 G = (V, E) 被称为二分图，如果其顶点集 V 可以被划分为两个不相交的子集 U 和 V ，使得每条边 e 属于 E 都连接一个 U 中的顶点和一个 V 中的顶点。

性质

1. 两色定理：一个图是二分图，当且仅当它可以用两种颜色对顶点进行着色，使得每条边的两个顶点的颜色不同。这也称为图的着色问题。
2. 无奇环性：一个图是二分图，当且仅当它不包含奇数长度的环。

注意：

• 二分图不一定是连通的。
• 多个孤立的顶点也是二分图。