Bipartite Graphs | 二部图

📚 Bipartite Graphs | 二部图

In Edexcel A-Level Decision Mathematics, bipartite graphs are a core modelling tool used to represent relationships between two distinct sets of objects, such as workers and tasks or students and project choices. This article covers definitions, recognition, matchings, the maximum matching algorithm and Hall’s marriage theorem, with exam-focused guidance.

在Edexcel A-Level决策数学中，二部图是核心建模工具，用于表示两组不同对象之间的关系，例如工人与任务或学生与项目选择。本文涵盖定义、识别、匹配、最大匹配算法和霍尔婚配定理，并提供应试指导。

1. Introduction to Bipartite Graphs | 二部图简介

A bipartite graph is a graph whose vertices can be split into two disjoint sets X and Y so that every edge joins a vertex in X to a vertex in Y. No edge is allowed within X or within Y. This structure appears naturally in allocation problems.

二部图是指顶点可以分成两个不相交的集合X和Y，使得每条边都连接X中的一个顶点和Y中的一个顶点。在X内部或Y内部都不允许有边。这种结构自然出现在分配问题中。

For example, if X = {A, B, C} represents three students and Y = {P, Q, R} represents three projects, an edge between A and P means student A is interested in project P. The graph is bipartite because all edges cross between the two sets.

例如，若X = {A, B, C}表示三个学生，Y = {P, Q, R}表示三个项目，则A和P之间的边表示学生A对项目P感兴趣。该图为二部图，因为所有边都跨接两个集合。

2. Formal Definition and Notation | 正式定义与记号

Formally, a graph G = (V, E) is bipartite if its vertex set V can be written as V = X ∪ Y with X ∩ Y = ∅, and every edge e ∈ E has the form e = {x, y} where x ∈ X and y ∈ Y.

形式上，图G = (V, E)是二部图，如果其顶点集V可以写成V = X ∪ Y且X ∩ Y = ∅，并且每条边e ∈ E都具有e = {x, y}的形式，其中x ∈ X且y ∈ Y。

We often denote such a graph by G = (X, Y, E) to emphasise the two parts. The degree of a vertex still counts the number of edges incident to it, but in a bipartite graph all neighbours of a vertex in X lie in Y.

我们通常将这样的图记为G = (X, Y, E)，以强调两个部分。顶点的度仍然计算与它关联的边数，但在二部图中，X中顶点的所有邻点都在Y中。

3. Recognising Bipartite Graphs | 识别二部图

A useful theorem states: a graph is bipartite if and only if it contains no cycle of odd length. An odd cycle has 3, 5, 7, … edges. This gives a quick visual test for small graphs.

一个有用的定理指出：一个图是二部图当且仅当它不含奇数长度的环。奇环有3、5、7…条边。这为小图提供了快速目测检验。

To prove a graph is bipartite, you can apply two-colouring: start at any vertex, colour it red, colour all its neighbours blue, then colour their neighbours red, and so on. If no vertex receives two different colours, the graph is bipartite.

要证明一个图是二部图，可以使用二染色法：从任意顶点开始将其染为红色，将其所有邻点染为蓝色，再将蓝色顶点的邻点染为红色，依此类推。如果没有顶点同时得到两种颜色，则该图是二部图。

If a conflict occurs, you have found an odd cycle. In exams, a two-colouring argument is often accepted as a rigorous justification.

如果出现冲突，则找到了一个奇环。在考试中，二染色论证通常被接受为严格的证明。

4. Complete Bipartite Graphs Kₘ,ₙ | 完全二部图 Kₘ,ₙ

If every vertex in X is connected to every vertex in Y, the graph is a complete bipartite graph, denoted Kₘ,ₙ where m = |X| and n = |Y|.

如果X中的每个顶点都与Y中的每个顶点相连，则该图是完全二部图，记为Kₘ,ₙ，其中m = |X|，n = |Y|。

The total number of edges in Kₘ,ₙ is m × n. For example, K₂,₃ has 2 × 3 = 6 edges.

Published by TutorHao | A-Level Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）