普通图 vs 二部图

概述

普通图（General Graph）对顶点间的连边没有限制，任意两个顶点之间都可以有边。二部图（Bipartite Graph）是一种特殊图，其顶点集可以划分为两个互不相交的独立集，所有边只能跨越两个集合。二部图的核心特征是不包含奇数长度的环，等价于其色数 $\chi (G)\le 2$。

定义

普通图

图 $G=(V,E)$ 中，边集 $E$ 是 $V$ 中元素的无序对的集合（无向图）。任意两个不同顶点之间都可以有边相连，没有额外的结构约束。这是图的最一般形式，包含完全图、环图、树等所有特殊图作为特例。

二部图

图 $G=(V,E)$ 称为二部图，当且仅当存在 $V$ 的一个划分 $V=L\cup R$（$L\cap R=\varnothing$），使得每条边的两个端点分别属于不同的集合。即边只在 $L$ 和 $R$ 之间，$L$ 和 $R$ 内部没有边。通常记为 $G=(L,R,E)$。

对比维度

维度	普通图	二部图
顶点划分	无要求	顶点可划分为两个独立集 $L$ 和 $R$
边的限制	任意顶点间可有边	边只能跨越 $L$ 和 $R$
奇数环	可以包含奇数环	不包含任何奇数长度的环
色数	任意（$\chi (G)\ge 1$）	$\chi (G)\le 2$
邻接矩阵	一般形式	可写为分块矩阵 $\left(\begin{array}{cc}0& B\\ B^T& 0\end{array}\right)$
判定方法	无需判定	BFS/DFS 染色法，$O(V+E)$
匹配理论	一般匹配问题复杂	König 定理、Hall 定理等丰富理论
典型例子	完全图 $K_n$、环 $C_n$	完全二部图 $K_{m,n}$、树

关键区别

• 普通图允许任意连边，二部图要求所有边跨越两个独立集——这是结构上的根本约束
• 二部图不包含奇数环，这是其最重要的等价刻画；普通图可以包含任意长度的环
• 二部图上的匹配问题（如最大匹配）有丰富的理论工具（König 定理、Hall 定理），一般图上的匹配问题更为复杂
• 所有树都是二部图（因为树无环，自然不含奇数环），但并非所有二部图都是树
• 二部图的色数不超过 2，普通图的色数可以任意大（如完全图 $K_n$ 的色数为 $n$）

联系

• 二部图是普通图的特例，所有二部图的性质在普通图中也成立
• 任何普通图都可以通过检查是否包含奇数环来判定是否为二部图
• 二部图在匹配、覆盖、着色等问题上有更丰富的理论结果
• 完全二部图 $K_{m,n}$ 有 $m\times n$ 条边，是完全图 $K_{m+n}$ 的子图
• 二部图在任务分配、课程安排、社交网络分析等场景中有广泛应用

参见

• 二部图 — 二部图的完整概念卡片
• 图论 — 图论的基本概念与分类