bipartite graph
二部图
Meaning in context
A simple graph is bipartite if its vertex set admits a partition into two disjoint parts such that every edge has one endpoint in each part.
若简单图的顶点集可分成两个不交部分，且每条边的两端分属两部分，则它是二部图。
Example
A four-cycle is bipartite, with alternating vertices in each part; a triangle is not.
Usage and distinctions
The parts need not have equal size, and vertices within a part have no edges between them. We allow an empty part.
Recommended reading in this subject · Preparation & skip guidance
Definition sources
- Keller and Trotter — Applied Combinatorics (2016)Section 14.2, opening bipartite-graph and independent-part description · Checked 2026-10-14
Translation sources
- 南京大学计算机科学与技术系 — 二部图中的匹配，离散数学课程组slide 3 / PDF p.3「二部图(bipartite graph，偶图)」 · Checked 2026-10-14