霍尔婚配定理

二部圖中,一側頂點可全部匹配另一側的充要條件

数学上,霍尔婚配定理[注 1](英语:Hall's marriage theorem)是菲利浦·霍尔最先证明[3]图论定理,又称霍尔定理[4],描述二分图中,能将一侧全部顶点牵线匹配到另一侧的充要条件。定理另有一个等价的组合叙述,确定一族有限集合在何种充要条件下,可自每个集合各拣选一个元素,而使所选元素两两互异(即没有元素是重复的)。

集族表述

   的有限子集[注 2]组成的有限[注 3]多重[注 4]

  的一个代表系英语Transversal (combinatorics)  单射,且该单射   将族中任意集合   映至该集合的某元素  。换言之,   中每个集合,选出一个代表元,使得不同的集合由不同元素代表(“单射”之义)。代表系又称为“截面”或“遍历”(transversal)。

  满足霍尔条件,意思是对每个子族  ,有

 

用文字复述,该条件断言对于   的每个子族,其各集合一共拥有的不同成员数,不小于该子族的集合数。若不满足该条件,则不存在代表系,因为在某子族  (设有   个集合)中,各集合一共衹有少于   个互异元素,如此由鸽巢原理,为   个集合所选的   个代表元之中,必有两者相等。霍尔定理说明,前述命题的否命题也成立,即若满足霍尔条件,则必存在代表系。

霍尔定理:一族有限集有代表系,当且仅当其满足霍尔条件,即其任意子族皆满足以上不等式。

证明见§ 图论表述

 
例一:符合霍尔条件

例一:考虑集族  ,其中

 

合适的代表系有  ,但并不唯一,例如   亦可。

 
例二:违反霍尔条件

例二:考虑  ,其中

 

此时,无合适的代表系。子族   违反霍尔条件,因为该族有   个集合,但该三个集之并为  ,仅得两个元素。

例三:同样设  ,但换成

 

此时,   的代表必为   或逆序,从而   的代表须为  。所以,合适的代表系有且衹有   

命名

定理命名为“婚配”(marriage),是与以下例子有关。设有两组人,一组   男,一组   女。每名女士心目中皆有一份名单(若干男士组成的子集),会接受名单中的男士的求婚,但会拒绝其他人。而该些男士别无所求,愿意向任何女士求婚。媒人希望判断是否存在方案,在尊重诸位女士的意愿的前提下,将该两组人撮合成   对夫妻[注 5]

  表示第   名女士愿意接受的男士集合,则霍尔定理讲述,存在方案使每位女士与心仪对象结婚,且无重婚,当且仅当对于任意若干位女士组成的集合  ,愿意与其中至少一位女士结婚的男士数  ,不小于该集合的女士数  

后一个条件为必要,否则该   名女士根本无法找到足够的配偶。较不明显的是,该条件亦为充分,此即霍尔定理的肯綮。

图论表述

 
蓝色边构成一组匹配

  为有限二部图,顶点集分为    两部,以符号记为    完美匹配是图上若干条边组成的匹配,其两两无公共端点,且   的每个顶点各有一条边在该匹配中。

对于   的任意子集  ,设     中的邻域英语Neighbourhood (graph theory),即   中与   至少一点有连边的全体顶点之集。霍尔定理断言,存在   完美匹配,当且仅当  的每个子集  ,皆有:

 

换言之,与   相邻的顶点,不少于   的顶点。上述不等式称为霍尔条件。

证明

 ”:假设有匹配  覆盖顶点集  。欲证霍尔条件对全部   成立。记     匹配到的顶点集,其为   的子集。由匹配的定义,必有  ,同时  ,因为   的元素皆为   的邻舍。故  ,即  

 ”:假设无   完美匹配,欲证有某子集   违反霍尔条件。设   为极大匹配,换言之,若再添加任何一条边,则不再为匹配。设    中未获覆盖的顶点。考虑由   出发的全体“交错路径”,即图   中的路径,其首边不属  ,次边属于  ,第三边又不属  ,如此交错排列。  藉该些交错路径,与   中若干顶点相连,该些顶点组成的子集记为  ;又与   中若干顶点相连(此处   亦视为与自己相连),得子集  。极长[注 6]的交错路径不能终于  ,否则其首尾皆不属  ,故为“增广路径”:翻转路径上所有边的状态,将不属   者加入  ,属   者移走,则得到严格比   多边的匹配,此为不可能。至此,已证   中每个顶点,皆经   匹配到   中某顶点。反之,  中任意一个顶点,亦有   中某顶点与之匹配,即沿    的交错路径,  的前一顶点。所以,  给出    之间的一一对应,所以  。另一方面,将证明  。设   是与某顶点   邻接。若边    中,则自    的一切交错路径中,  皆在   以先,故有    的交错路径。否则   不属  ,但已知有    的交错路径,末边属于  ,故可续以  ,亦得自    的交错路径。证毕  ,故  ,违反霍尔条件。

算法

  的子集   满足  ,则定义  霍尔犯英语Hall violator。若   为霍尔犯,则无匹配能覆盖   的全部顶点。所以,也无匹配覆盖  。霍尔定理断言,二部图有   完美匹配,当且仅当其不含任何霍尔犯。以下算法验证定理较难的方向:输入一幅二部图,算法或输出一个   完美匹配,或输出一个霍尔犯。

该算法调用以下子程序:输入匹配   及未匹配的某顶点  ,或输出一条   增广路径,或输出一个霍尔犯。该子程序可以深度优先搜索实作。

以下叙述算法的步骤:

  1. 初始时,设   为空集,未选定任何边。(其后会加边入  。)
  2. 检查:  确为   的匹配。
  3.   已覆盖  ,则为所求的   完美匹配,输出并结束程序。
  4. 否则,找到未匹配的顶点  
  5. 调用寻找增广路径的子程序,视乎情况:
    1. 若找到霍尔犯,则输出并结束。
    2. 若找到   增广路径,则将该路径上各边的状态翻转,使   的边数增加一。返回第2步。

每次找到增广路径,都会使   多一条边。所以,前述算法的回圈至多执行   次,就会停机。每次寻找增广路径需时  。总时间复杂度与不加权的最大匹配问题英语maximum cardinality matching福特-富尔克森算法相约。

两种表述等价

 ,其中   皆为有限集,不必相异。相应地,构造二部图  ,一侧顶点集   对应该   个集合,另一侧顶点集   为该些集合之并。若   有元素  ,则在图中连一条边  。如此,族   的代表系即是    完美匹配,覆盖   的全部顶点。所以,以集族表述的霍尔问题,容易化成图论表述的霍尔问题。反之亦然:给定二部图    完美匹配相当于邻域英语Neighbourhood (graph theory)  的代表系。

其他证明

利用拓扑组合学英语Topological combinatorics斯佩纳引理英语Sperner's lemma,可得霍尔定理的非构造性证明[5]:Thm.4.1,4.2

应用

定理有许多“非婚”应用。例如,取一叠啤牌(无鬼牌),洗匀后,派成13磴,每磴4张。由霍尔定理可证,必能从每磴拣选一张牌,使所选13张牌恰好出齐各点数(A、2、3、⋯⋯、Q、K)。更一般地,任意正则二部图(允许重边)皆有完美匹配。[6]:2

较抽象的应用有双边陪集遍历。设    为其有限指数子群,则霍尔定理适用于证明存在集合  ,既是   各左陪集的代表系,又是各右陪集的代表系。[7]

霍尔定理亦用于证明,若  ,则任意   拉丁矩阵英语Latin rectangle皆可扩展成   拉丁矩阵,并可重复,直至得到完整的拉丁方阵[8]

相关定理

本定理可归类到组合学的一列强力定理,其彼此关联。若假设任何一条,则较易证得其他各条,但若要从头开始,则较难证得任何一条。总括而言,该类定理各自断言某类组合优化问题具有强对偶性英语Strong duality。该些定理包括:

欲要更具体[9][10]描述各定理的关系,下列各等价关系有简单证明:

迪尔沃思定理 ⇔ 霍尔定理 ⇔ 克尼格-艾盖瓦里定理 ⇔ 克尼格定理。

加强

无穷族

马歇尔·霍尔英语Marshall Hall (mathematician)细察菲利浦·霍尔[注 9]原先的证明,发现可以将结论修改成对(有限集组成的)无穷族   仍成立。[11]该证明直接使用佐恩引理。此外,也有较简短的证明,用到命题逻辑紧致性定理[12]

 。对每个   ,以命题   表示“  选为   的代表”。可以列出代表系须满足的条件如下:

  • 对应每个  ,各有一条命题断言恰有一个   使   为真[注 10]
  • 对应每对互异的   ,各有一条命题为  

如此,代表系即等价于同时满足以上各命题的赋值。由有限族的霍尔定理,对   的任意有限子集  ,相应的有限子族有代表系,故以上命题中,任意有限条皆可同时满足。所以,由紧致性定理,全部命题可同时满足,即有整个无穷族的代表系。

以上一般情况的证明中,选择公理(或等价命题如佐恩引理)为必须,因为给定一族无穷多个非空集(无额外条件),欲从每个集合中,选出一个代表(而无须相异),已需要选择公理。

无穷集

马歇尔·霍尔给出下列反例,表明若允许有无穷集,则所组成的无穷族,即使满足霍尔条件,亦不保证有代表系。

设族  可数多个集合   构成。该族满足霍尔条件,但无法选出代表系。[11]

若妥为叙述,则的确可将霍尔定理推广至适用于无穷集。给定二部图,两侧顶点集为  ,若由   的子集   出发,在图中找到单射(意思是衹能用二部图的边),射向   的子集  ,则称  ,而若更甚者,图中没有反向的,由    的单射,则称  。前述定义中,若忽略“在图中”三字,则所得大小的概念等同一般基数的大小比较。无穷集的婚配定理断言:[13]

图中有    的单射,当且仅当对每个  ,皆有其邻域  

代表系的数目

马歇尔·霍尔也计算出给定有限族   的代表系数目的下界,从而加强婚配定理。其叙述为:[14]

设有一列有限集  ,不必相异,但满足霍尔条件,又设    成立。则当   时,该族有限集至少有   个不同的代表系,而当   时,至少有   个。

此处即使两个代表系的元素一样,衹要其次序不同,亦视为不同。例如,若   ,则    为两个不同的代表系。

分数匹配

图的分数匹配fractional matching)是对各边赋予非负权值,使每个顶点所连各边的权值和不超逾  。所谓   完美的分数匹配,即是使   中的每一顶点处,各边权之和恰为  。对于二部图  ,下列各项等价:[15]

  •    完美匹配。
  •    完美分数匹配。(此为前项的直接推论。给定一个   完美匹配,将该匹配所选的边赋权  ,其馀边赋  ,则得到   完美分数匹配。)
  •   满足霍尔条件。(若有前项的分数匹配,则对于   的每个子集  ,其所连各边之和恰为  ,故至少要与对面的   个顶点相连,因为对面每个顶点所连的边值和不超过  。)

亏缺

假如霍尔条件不成立,则原定理仅断言不存在完美匹配,但并未说明匹配最大可以多大。欲知此事,需要考虑图的亏度英语Deficiency (graph theory)。对于二部图    关于  亏度deficiency)是   的最大值,其中   可取   的任意子集。亏度越大,则图离霍尔条件越远。

用霍尔定理可证,若二部图的亏度为  ,则有大小为   的匹配。(考虑在   侧添加   个辅助点,与   所有顶点连边。新图将满足霍尔条件。)

非二部图

  1. ^ 婚配之名见于[1][2]
  2. ^ Hall, Jr. 1986,pg. 51。也可以允许无穷集,但此时须限制族中的集合数有限(考虑重数),见§ 推广。然而,不能放宽成无穷多个无穷集。
  3. ^   可以放宽为无穷族,见§ 推广
  4. ^   可以有重复的元素,且会考虑其重复次数
  5. ^ 此例子中,为使定理适用,需要假设该些人的婚姻为一夫一妻制
  6. ^ 即无法再延伸。
  7. ^ 定理的名称,文献中略有出入。相关的定理既有二分图匹配的表述,也有 (0,1) 矩阵覆盖的表述。Hall, Jr. (1986)van Lint & Wilson (1992)称矩阵表述为克尼格定理,而Roberts & Tesman (2009)则称之为克尼格-艾盖瓦里定理。二部图版本,Cameron (1994)Roberts & Tesman (2009)皆称为克尼格定理。
  8. ^ 即行和与列和皆等于一,且各项非负。
  9. ^ 两人并非亲属。
  10. ^ 此处的命题需要   为有限集,才能用命题逻辑的语言写出

参考文献

  1. ^ 毛华; 庞双杰. Hall婚配定理的新证明方法. 河北大学学报(自然科学版). 2008, 28 (2): 127–129. doi:10.3969/j.issn.1000-1565.2008.02.005. 
  2. ^ 王树禾. 前言. 图论. 21世纪高等院校教材·信息与计算科学专业教材系列. 北京: 科学出版社. 2004: ii. ISBN 7-03-012423-5. 
  3. ^ Hall, Philip. On Representatives of Subsets [论子集之代表元]. J. London Math. Soc. 1935, 10 (1): 26–30. doi:10.1112/jlms/s1-10.37.26 (英语). 
  4. ^ 张鸿林; 葛显良. 英汉数学词汇. 清华大学出版社. 2005: 299. 
  5. ^ 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) (英语). 
  6. ^ DeVos, Matt. Graph Theory [图论] (PDF). Simon Fraser University. [2021-12-03]. (原始内容 (PDF)存档于2021-12-03) (英语). 
  7. ^ 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. 
  8. ^ Hall, Marshall. An existence theorem for latin squares [拉丁方阵之存在定理]. Bull. Amer. Math. Soc. 1945, 51: 387–388. doi:10.1090/S0002-9904-1945-08361-X (英语). 
  9. ^ Borgersen, Robert D. Equivalence of seven major theorems in combinatorics [组合学七大定理之等价] (PDF). 2004-11-26 [2021-12-04]. (原始内容 (PDF)存档于2021-05-07) (英语). 
  10. ^ Reichmeider 1984
  11. ^ 11.0 11.1 Hall, Jr. 1986,pg. 51
  12. ^ Cameron 1994,sec. 19.5
  13. ^ 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 (英语). 
  14. ^ Cameron 1994,p. 90
  15. ^ co.combinatorics - Fractional Matching version of Hall's Marriage theorem [co.组合学——霍尔婚配定理分数匹配版]. MathOverflow. [2020-06-29]. (原始内容存档于2022-07-26) (英语). 

站外链结

本条目含有来自PlanetMathproof of Hall's marriage theorem》的内容,版权遵守知识共享协议:署名-相同方式共享协议