Bipartite Graph

释义 Definition

二分图（双部图）：一种图（graph），其顶点集合可以被划分为两个互不相交的部分 (U) 和 (V)，并且每条边都只连接 (U) 中的顶点与 (V) 中的顶点（同一部分内部不连边）。常用于描述“两个类别之间的关系”，例如“学生—课程”“用户—商品”等。
（该词在更广泛语境里还会出现“二分/两部分”的含义，但在计算机与数学中最常见的是图论定义。）

发音 Pronunciation (IPA)

/baɪˈpɑːrtaɪt ɡræf/

例句 Examples

A bipartite graph can be colored with just two colors.
二分图只需要两种颜色就可以完成染色。

In a bipartite graph, finding a maximum matching helps pair as many users with items as possible without conflicts.
在二分图中，寻找最大匹配可以在不冲突的情况下尽可能多地把用户与物品配对。

词源 Etymology

bipartite 来自拉丁语前缀 bi-（“二、两个”）+ partite（与“部分/划分”有关，源自 part- “部分”），字面意思是“分成两部分的”。graph 源自希腊语 *graph-*（“写/画”），在现代数学里引申为“图（由点和边构成的结构）”。合在一起即“可分成两部分的图”。

相关词 Related Words

• Bipartite
• Graph
• Vertex
• Edge
• Partition
• Matching
• 2-Coloring
• Complete Bipartite Graph

文学与经典著作 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在匹配（matching）、网络流（flow）等章节中频繁使用二分图建模。
• Graph Theory（Douglas B. West）：系统介绍二分图性质、二部划分与相关定理（如匹配理论中的经典结果）。
• Graph Theory（Reinhard Diestel）：在图的染色、匹配与结构性讨论中多处涉及二分图与等价刻画（如“无奇环”）。