📚 Bipartisanship | 两党合作与二分图
In politics, 'bipartisanship' embodies cooperation between two opposing parties, yet within A‑Level Mathematics — particularly in Edexcel Decision 1 — a strikingly similar term ‘bipartite’ defines a graph whose vertices can be split into two sets with edges only crossing between them. This article uses that linguistic bridge to explore bipartite graphs, matching algorithms, and their real‑world optimisation power, all firmly rooted in your syllabus.
在政治中，“两党合作”体现对立两党的协作；而在 A‑Level 数学，尤其是 Edexcel D1 里，一个读音相仿的词“二分图”描述的是一种顶点可以分成两个集合、边只跨越集合之间的图。本文借由这个语言桥梁深入讲解二分图、匹配算法及其现实优化威力，全部紧扣你的考纲。
1. What Is a Bipartite Graph? | 什么是二分图？
A bipartite graph is a graph whose vertex set can be partitioned into two disjoint sets X and Y such that every edge joins a vertex in X to a vertex in Y. No edge connects vertices within the same set.
二分图是一种顶点集可以划分成两个不相交集合 X 与 Y，且每条边都连接 X 中的一个顶点和 Y 中的一个顶点的图。同一集合内的顶点之间没有边相连。
2. Recognising Bipartite Graphs | 识别二分图
You can check if a graph is bipartite by attempting to colour its vertices with two colours so that adjacent vertices receive different colours. If the graph contains an odd cycle, it cannot be bipartite.
你可以尝试用两种颜色给顶点着色，使得相邻顶点颜色不同，如果图包含奇环，则它不可能是二分图。
3. Why Bipartite Graphs Matter in Decision Maths | 二分图在决策数学中的意义
Bipartite graphs model assignment problems: workers to tasks, applicants to jobs, or projects to resources. They form the foundation of the Hungarian algorithm and Hall's marriage theorem.
二分图可建模指派问题：工人与任务、申请者与职位、项目与资源。它是匈牙利算法和霍尔婚姻定理的基础。
4. Setting Up a Bipartite Graph | 建立二分图
Charlie}, right set Y = {Task 1, Task 2, Task 3}. Draw an edge if a person can do a task.
将两个不同的集合列在两侧。例如左集 X = {Alice, Bob, Charlie}，右集 Y = {Task 1, Task 2, Task 3}。若某人能完成某项任务，则连一条边。
5. Matching in a Bipartite Graph | 二分图中的匹配
A matching is a set of edges without common vertices. A maximum matching contains as many edges as possible. A complete matching covers every vertex in the smaller set.
匹配是一组没有公共顶点的边集。最大匹配包含尽可能多的边。完全匹配覆盖较小集合中的所有顶点。
6. Hall's Marriage Theorem – The Core Criterion | 霍尔婚姻定理——核心判据
Hall' y if for every subset A of X, the number of vertices in the neighbourhood of A is at least |A|. Formally: |N(A)| ≥ |A|.
霍尔定理指出，从 X 到 Y 存在完全匹配，当且仅当对于 X 的任意子集 A，其邻域 N(A) 中的顶点数不小于 |A|。正式表述为 |N(A)| ≥ |A|。
7. Applying Hall's Condition in an Exam | 考试中应用霍尔条件
To prove a complete matching is impossible, find a subset A where |N(A)| < |A|. To prove it is possible, show the condition holds for all subsets, or construct the matching using an algorithm.
要证明完全匹配不可能，找出一个子集 A 使 |N(A)| < |A|。要证明可能，需证明所有子集满足条件，或通过算法构造出匹配。
8. The Alternating Path Algorithm | 交替路径算法
Start with an initial matching. Find an alternating path from an unmatched vertex in X to an unmatched vertex in Y, then flip the edges along the path to increase the matching size by 1. Repeat until no more augmenting paths exist.
从初始匹配开始。寻找从 X 中未匹配顶点到 Y 中未匹配顶点的交替路径，然后翻转路径上的边，使匹配数增加 1。重复直至不存在增广路径。
9. Maximum Matching in a Table | 表格中的最大匹配
Edexcel often presents a bipartite graph as an adjacency matrix or a table. Use the alternating path method on the matrix by marking initial assignments and looking for improvements.
Edexcel 常以邻接矩阵或表格形式给出二分图。在矩阵上标记初始指派，运用交替路径法寻找改进机会。
10. Real‑World Optimisation – From Politics to Logistics | 从政治到物流的现实优化
Just as bipartisanship requires parties to work across the aisle, bipartite matching allocates resources across two distinct groups, ensuring efficiency in scheduling, transport, and school admissions.
正如两党合作需要政党跨越隔阂协作，二分图匹配在两群人之间分配资源，确保调度、运输和学校招生上的高效运作。
11. Common Pitfalls and Exam Tips | 常见陷阱与考试技巧
Always label your vertex sets clearly. When applying Hall's theorem, test the most restrictive subsets first. For alternating paths, draw partial matchings neatly and track visited vertices to avoid infinite loops.
务必清晰标记顶点集。应用霍尔定理时，优先检验约束最强的子集。使用交替路径时，整齐画出部分匹配并记录已访问顶点以避免死循环。
12. Connecting Back to the Syllabus | 回归考纲
Edexcel Decision Mathematics 1 requires you to model problems using bipartite graphs, perform matching algorithms, and understand Hall's theorem. Mastering these tools turns a seemingly political word into a concrete mathematical asset.
Edexcel 决策数学 1 要求你使用二分图建模问题、执行匹配算法并理解霍尔定理。掌握这些工具，就能把一个看似政治的词汇转化为扎实的数学资产。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图