霍尔婚配定理
数学上,霍尔婚配定理[注 1](英语:Hall's marriage theorem)是菲利浦·霍尔最先证明[3]的图论定理,又称霍尔定理[4],描述二分图中,能将一侧全部顶点牵线匹配到另一侧的充要条件。定理另有一个等价的组合叙述,确定一族有限集合在何种充要条件下,可自每个集合各拣选一个元素,而使所选元素两两互异。
集族表述
设 为 的有限子集[注 2]组成的有限[注 3]多重[注 4]族。
的一个代表系是 至 的单射,且该单射 将族中任意集合 映至该集合的某元素 。换言之, 从 中每个集合,选出一个代表元,使得不同的集合由不同元素代表(“单射”之义)。代表系又称为“截面”或“遍历”(transversal)。
族 满足霍尔条件,意思是对每个子族 ,有
用文字复述,该条件断言对于 的每个子族,其各集合一共拥有的不同成员数,不小于该子族的集合数。若不满足该条件,则不存在代表系,因为在某子族 (设有 个集合)中,各集合一共衹有少于 个互异元素,如此由鸽巢原理,为 个集合所选的 个代表元之中,必有两者相等。霍尔定理说明,前述命题的否命题也成立,即若满足霍尔条件,则必存在代表系。
霍尔定理:一族有限集有代表系,当且仅当其满足霍尔条件,即其任意子族皆满足以上不等式。
证明见§ 图论表述。
例
例一:考虑集族 ,其中
合适的代表系有 ,但并不唯一,例如 亦可。
例二:考虑 ,其中
此时,无合适的代表系。子族 违反霍尔条件,因为该族有 个集合,但该三个集之并为 ,仅得两个元素。
例三:同样设 ,但换成
此时, 与 的代表必为 或逆序,从而 的代表须为 。所以,合适的代表系有且衹有 或 。
命名
定理命名为“婚配”(marriage),是与以下例子有关。设有两组人,一组 男,一组 女。每名女士心目中皆有一份名单(若干男士组成的子集),会接受名单中的男士的求婚,但会拒绝其他人。而该些男士别无所求,愿意向任何女士求婚。媒人希望判断是否存在方案,在尊重诸位女士的意愿的前提下,将该两组人撮合成 对夫妻[注 5]。
以 表示第 名女士愿意接受的男士集合,则霍尔定理讲述,存在方案使每位女士与心仪对象结婚,且无重婚,当且仅当对于任意若干位女士组成的集合 ,愿意与其中至少一位女士结婚的男士数 ,不小于该集合的女士数 。
后一个条件为必要,否则该 名女士根本无法找到足够的配偶。较不明显的是,该条件亦为充分,此即霍尔定理的肯綮。
图论表述
设 为有限二部图,顶点集分为 、 两部,以符号记为 。 完美匹配是图上若干条边组成的匹配,其两两无公共端点,且 的每个顶点各有一条边在该匹配中。
对于 的任意子集 ,设 为 在 中的邻域,即 中与 至少一点有连边的全体顶点之集。霍尔定理断言,存在 完美匹配,当且仅当对 的每个子集 ,皆有:
换言之,与 相邻的顶点,不少于 的顶点。上述不等式称为霍尔条件。
证明
“ ”:假设有匹配 ,覆盖顶点集 。欲证霍尔条件对全部 成立。记 为 经 匹配到的顶点集,其为 的子集。由匹配的定义,必有 ,同时 ,因为 的元素皆为 的邻舍。故 ,即 。
“ ”:假设无 完美匹配,欲证有某子集 违反霍尔条件。设 为极大匹配,换言之,若再添加任何一条边,则不再为匹配。设 为 中未获覆盖的顶点。考虑由 出发的全体“交错路径”,即图 中的路径,其首边不属 ,次边属于 ,第三边又不属 ,如此交错排列。 藉该些交错路径,与 中若干顶点相连,该些顶点组成的子集记为 ;又与 中若干顶点相连(此处 亦视为与自己相连),得子集 。极长[注 6]的交错路径不能终于 ,否则其首尾皆不属 ,故为“增广路径”:翻转路径上所有边的状态,将不属 者加入 ,属 者移走,则得到严格比 多边的匹配,此为不可能。至此,已证 中每个顶点,皆经 匹配到 中某顶点。反之, 中任意一个顶点,亦有 中某顶点与之匹配,即沿 至 的交错路径, 的前一顶点。所以, 给出 与 之间的一一对应,所以 。另一方面,将证明 。设 是与某顶点 邻接。若边 在 中,则自 至 的一切交错路径中, 皆在 以先,故有 至 的交错路径。否则 不属 ,但已知有 至 的交错路径,末边属于 ,故可续以 ,亦得自 至 的交错路径。证毕 ,故 ,违反霍尔条件。
算法
若 的子集 满足 ,则定义 为霍尔犯。若 为霍尔犯,则无匹配能覆盖 的全部顶点。所以,也无匹配覆盖 。霍尔定理断言,二部图有 完美匹配,当且仅当其不含任何霍尔犯。以下算法验证定理较难的方向:输入一幅二部图,算法或输出一个 完美匹配,或输出一个霍尔犯。
该算法调用以下子程序:输入匹配 及未匹配的某顶点 ,或输出一条 增广路径,或输出一个霍尔犯。该子程序可以深度优先搜索实作。
以下叙述算法的步骤:
- 初始时,设 为空集,未选定任何边。(其后会加边入 。)
- 检查: 确为 的匹配。
- 若 已覆盖 ,则为所求的 完美匹配,输出并结束程序。
- 否则,找到未匹配的顶点 。
- 调用寻找增广路径的子程序,视乎情况:
- 若找到霍尔犯,则输出并结束。
- 若找到 增广路径,则将该路径上各边的状态翻转,使 的边数增加一。返回第2步。
每次找到增广路径,都会使 多一条边。所以,前述算法的循环至多执行 次,就会停机。每次寻找增广路径需时 。总时间复杂度与不加权的最大匹配问题的福特-富尔克森算法相约。
两种表述等价
设 ,其中 皆为有限集,不必相异。相应地,构造二部图 ,一侧顶点集 对应该 个集合,另一侧顶点集 为该些集合之并。若 有元素 ,则在图中连一条边 。如此,族 的代表系即是 的 完美匹配,覆盖 的全部顶点。所以,以集族表述的霍尔问题,容易化成图论表述的霍尔问题。反之亦然:给定二部图 , 完美匹配相当于邻域族 的代表系。
其他证明
应用
定理有许多“非婚”应用。例如,取一叠啤牌(无鬼牌),洗匀后,派成13磴,每磴4张。由霍尔定理可证,必能从每磴拣选一张牌,使所选13张牌恰好出齐各点数(A、2、3、⋯⋯、Q、K)。更一般地,任意正则二部图(允许重边)皆有完美匹配。[6]:2
较抽象的应用有双边陪集遍历。设 为群, 为其有限指数子群,则霍尔定理适用于证明存在集合 ,既是 各左陪集的代表系,又是各右陪集的代表系。[7]
相关定理
本定理可归类到组合学的一列强力定理,其彼此关联。若假设任何一条,则较易证得其他各条,但若要从头开始,则较难证得任何一条。总括而言,该类定理各自断言某类组合优化问题具有强对偶性。该些定理包括:
- 克尼格定理:二部图的最大匹配,与最小顶点覆盖等大。
- 克尼格-艾盖瓦里定理(1931年),得名自克尼格·代奈什、艾盖瓦里·耶内两位匈牙利数学家,是克尼格定理的加权推广。[注 7]
- 门格尔定理(1927年):边最小割的大小,等于任意在所有顶点对之间可以找到的无公共边的路径的最大数量。结论换成顶点最小割与无公共(中间)顶点的路径仍成立。
- 最大流最小割定理(福特-富尔克森算法):任意网络流中,最大流的值等于最小割。
- 伯克霍夫-冯纽曼定理(1946年):一个方阵为双随机[注 8],当且仅当其为置换方阵的凸组合。
- 迪尔沃思定理:覆盖某偏序集所需的不交链数,与该集的最大反链等大。
欲要更具体[9][10]描述各定理的关系,下列各等价关系有简单证明:
迪尔沃思定理 ⇔ 霍尔定理 ⇔ 克尼格-艾盖瓦里定理 ⇔ 克尼格定理。
加强
无穷族
马歇尔·霍尔细察菲利浦·霍尔[注 9]原先的证明,发现可以将结论修改成对(有限集组成的)无穷族 仍成立。[11]该证明直接使用佐恩引理。此外,也有较简短的证明,用到命题逻辑的紧致性定理:[12]
设 。对每个 和 ,以命题 表示“ 选为 的代表”。可以列出代表系须满足的条件如下:
- 对应每个 ,各有一条命题断言恰有一个 使 为真[注 10];
- 对应每对互异的 和 ,各有一条命题为 。
如此,代表系即等价于同时满足以上各命题的赋值。由有限族的霍尔定理,对 的任意有限子集 ,相应的有限子族有代表系,故以上命题中,任意有限条皆可同时满足。所以,由紧致性定理,全部命题可同时满足,即有整个无穷族的代表系。
以上一般情况的证明中,选择公理(或等价命题如佐恩引理)为必须,因为给定一族无穷多个非空集(无额外条件),欲从每个集合中,选出一个代表(而无须相异),已需要选择公理。
无穷集
马歇尔·霍尔给出下列反例,表明若允许有无穷集,则所组成的无穷族,即使满足霍尔条件,亦不保证有代表系。
设族 由可数多个集合 构成。该族满足霍尔条件,但无法选出代表系。[11]
若妥为叙述,则的确可将霍尔定理推广至适用于无穷集。给定二部图,两侧顶点集为 ,若由 的子集 出发,在图中找到单射(意思是衹能用二部图的边),射向 的子集 ,则称 ,而若更甚者,图中没有反向的,由 至 的单射,则称 。前述定义中,若忽略“在图中”三字,则所得大小的概念等同一般基数的大小比较。无穷集的婚配定理断言:[13]
图中有 至 的单射,当且仅当对每个 ,皆有其邻域 。
代表系的数目
马歇尔·霍尔也计算出给定有限族 的代表系数目的下界,从而加强婚配定理。其叙述为:[14]
设有一列有限集 ,不必相异,但满足霍尔条件,又设 对 成立。则当 时,该族有限集至少有 个不同的代表系,而当 时,至少有 个。
此处即使两个代表系的元素一样,衹要其次序不同,亦视为不同。例如,若 , ,则 和 为两个不同的代表系。
分数匹配
图的分数匹配(fractional matching)是对各边赋予非负权值,使每个顶点所连各边的权值和不超逾 。所谓 完美的分数匹配,即是使 中的每一顶点处,各边权之和恰为 。对于二部图 ,下列各项等价:[15]
- 有 完美匹配。
- 有 完美分数匹配。(此为前项的直接推论。给定一个 完美匹配,将该匹配所选的边赋权 ,其余边赋 ,则得到 完美分数匹配。)
- 满足霍尔条件。(若有前项的分数匹配,则对于 的每个子集 ,其所连各边之和恰为 ,故至少要与对面的 个顶点相连,因为对面每个顶点所连的边值和不超过 。)
亏缺
假如霍尔条件不成立,则原定理仅断言不存在完美匹配,但并未说明匹配最大可以多大。欲知此事,需要考虑图的亏度。对于二部图 , 关于 的亏度(deficiency)是 的最大值,其中 可取 的任意子集。亏度越大,则图离霍尔条件越远。
用霍尔定理可证,若二部图的亏度为 ,则有大小为 的匹配。(考虑在 侧添加 个辅助点,与 所有顶点连边。新图将满足霍尔条件。)
非二部图
注
- ^ 婚配之名见于[1][2]。
- ^ Hall, Jr. 1986,pg. 51。也可以允许无穷集,但此时须限制族中的集合数有限(考虑重数),见§ 推广。然而,不能放宽成无穷多个无穷集。
- ^ 可以放宽为无穷族,见§ 推广。
- ^ 即 可以有重复的元素,且会考虑其重复次数。
- ^ 此例子中,为使定理适用,需要假设该些人的婚姻为一夫一妻制。
- ^ 即无法再延伸。
- ^ 定理的名称,文献中略有出入。相关的定理既有二分图匹配的表述,也有 (0,1) 矩阵覆盖的表述。Hall, Jr. (1986)和van Lint & Wilson (1992)称矩阵表述为克尼格定理,而Roberts & Tesman (2009)则称之为克尼格-艾盖瓦里定理。二部图版本,Cameron (1994)和Roberts & Tesman (2009)皆称为克尼格定理。
- ^ 即行和与列和皆等于一,且各项非负。
- ^ 两人并非亲属。
- ^ 此处的命题需要 为有限集,才能用命题逻辑的语言写出
参考文献
- ^ 毛华; 庞双杰. Hall婚配定理的新证明方法. 河北大学学报(自然科学版). 2008, 28 (2): 127–129. doi:10.3969/j.issn.1000-1565.2008.02.005.
- ^ 王树禾. 前言. 图论. 21世纪高等院校教材·信息与计算科学专业教材系列. 北京: 科学出版社. 2004: ii. ISBN 7-03-012423-5.
- ^ Hall, Philip. On Representatives of Subsets [论子集之代表元]. J. London Math. Soc. 1935, 10 (1): 26–30. doi:10.1112/jlms/s1-10.37.26 (英语).
- ^ 张鸿林; 葛显良. 英汉数学词汇. 清华大学出版社. 2005: 299.
- ^ Haxell, P. On Forming Committees [论委员会之组成]. The American Mathematical Monthly. 2011, 118 (9): 777–788 [2021-12-03]. ISSN 0002-9890. doi:10.4169/amer.math.monthly.118.09.777. (原始内容存档于2021-12-03) (英语).
- ^ DeVos, Matt. Graph Theory [图论] (PDF). Simon Fraser University. [2021-12-03]. (原始内容 (PDF)存档于2021-12-03) (英语).
- ^ Button, Jack; Chiodo, Maurice; Zeron-Medina Laris, Mariano. Coset Intersection Graphs for Groups [群的陪集相交图]. The American Mathematical Monthly. 2014, 121 (10): 922–26. doi:10.4169/amer.math.monthly.121.10.922 (英语).
For H a finite index subgroup of G, the existence of a left-right transversal is well known, sometimes presented as an application of Hall’s marriage theorem.
- ^ Hall, Marshall. An existence theorem for latin squares [拉丁方阵之存在定理]. Bull. Amer. Math. Soc. 1945, 51: 387–388. doi:10.1090/S0002-9904-1945-08361-X (英语).
- ^ Borgersen, Robert D. Equivalence of seven major theorems in combinatorics [组合学七大定理之等价] (PDF). 2004-11-26 [2021-12-04]. (原始内容 (PDF)存档于2021-05-07) (英语).
- ^ Reichmeider 1984
- ^ 11.0 11.1 Hall, Jr. 1986,pg. 51
- ^ Cameron 1994,sec. 19.5
- ^ Aharoni, Ron. König's Duality Theorem for Infinite Bipartite Graphs [无穷二部图的克尼格对偶定理]. Journal of the London Mathematical Society. February 1984, s2–29 (1): 1–12. ISSN 0024-6107. doi:10.1112/jlms/s2-29.1.1 (英语).
- ^ Cameron 1994,p. 90
- ^ co.combinatorics - Fractional Matching version of Hall's Marriage theorem [co.组合学——霍尔婚配定理分数匹配版]. MathOverflow. [2020-06-29]. (原始内容存档于2022-07-26) (英语).
- Brualdi, Richard A., Introductory Combinatorics [入门组合学], Upper Saddle River, NJ: Prentice-Hall/Pearson, 2010, ISBN 978-0-13-602040-0 (英语)
- Cameron, Peter J., Combinatorics: Topics, Techniques, Algorithms [组合学:问题、技巧、算法], Cambridge: Cambridge University Press, 1994, ISBN 978-0-521-45761-3 (英语)
- Dongchen, Jiang; Nipkow, Tobias, Hall's Marriage Theorem [霍尔婚配定理], The Archive of Formal Proofs, 2010 [2021-12-15], ISSN 2150-914X, (原始内容存档于2016-03-19) (英语). 经电脑验证的证明。
- Hall, Jr., Marshall, Combinatorial Theory [组合理论] 2nd, New York: John Wiley & Sons, 1986, ISBN 978-0-471-09138-7 (英语)
- Hall, Philip, On Representatives of Subsets [论子集的代表元], J. London Math. Soc., 1935, 10 (1): 26–30, doi:10.1112/jlms/s1-10.37.26 (英语)
- Halmos, Paul R.; Vaughan, Herbert E., The marriage problem [婚配问题], American Journal of Mathematics, 1950, 72 (1): 214–215, JSTOR 2372148, MR 0033330, doi:10.2307/2372148 (英语)
- Reichmeider, P.F., The Equivalence of Some Combinatorial Matching Theorems [若干组合匹配问题之等价], Polygonal Publishing House, 1984, ISBN 978-0-936428-09-3 (英语)
- Roberts, Fred S.; Tesman, Barry, Applied Combinatorics [应用组合学] 2nd, Boca Raton: CRC Press, 2009, ISBN 978-1-4200-9982-9 (英语)
- van Lint, J. H.; Wilson, R.M., A Course in Combinatorics [组合学教程], Cambridge: Cambridge University Press, 1992, ISBN 978-0-521-42260-4 (英语)
站外链接
- Cut-the-knot站,Marriage Theorem (页面存档备份,存于互联网档案馆)
- Cut-the-knot站,Marriage Theorem and Algorithm (页面存档备份,存于互联网档案馆)
- Lucky的笔记Hall's marriage theorem explained intuitively (页面存档备份,存于互联网档案馆).
本条目含有来自PlanetMath《proof of Hall's marriage theorem》的内容,版权遵守知识共享协议:署名-相同方式共享协议。