论文总字数：5396字

摘 要

关键词：Hall定理,相异代表系,二部图匹配

Abstract：In this paper, we mainly study the Hall theorem, and give the relevant background of Hall theorem and the proof of the theorem. We use this theorem to solve some related problems in real life. Such as “matching problem ”, bipartite graph matching problem, Hungarian algorithm and so on.

Keywords：Hall theorem, system of distinct representative, Bipartite graph matching

目 录

1 前言……………………………………………………………………4

2 基本定义、定理及证明…………………………………………………4

3 例题讲解………………………………………………………………7

4 Hall定理的应用 ……………………………………………………8

参考文献…………………………………………………………………11

致谢 ………………………………………………………………………12

1 前言

霍尔最初的术语是:设置给定的任意集合和的任何有限系,以及表示完整元素集合的子集系的相异代表元的一个完全集.对C.D.R.后期文献的简要描述一般称为相异代表系,简称为S.D.R.（P. Hall,1904-1982）在1935年发表的子集代表元素中所指的不同元素的集合,有人指出,这个子集有一个C.D.R.,以下条件是充分的:即对于每个,任意选择一组子集,其中将包含至少一个元素.

Hall定理也被称为婚姻理论.婚姻问题是由德国数学家H.Weyl（1885-1955）首次提到的.后来,美国数学家Haermosi（P.R. Halmos,1916-2006）和H.E.Vaughan在婚姻问题（1950年）中提出了以下问题:假设每个男孩都认识一定数量的女孩,问一个男孩在什么条件下可以娶一个他认识的女孩？霍尔定理提供了任何一组男生必须至少认识一名女学生的解决方案.因此,霍尔定理的条件有时被称为婚姻条件.

2 基本定义、定理及证明

定义1（相异代表系） 设是一族集合,它们的一个相异代表系（简记为SDR）就是一个维向量满足如下条件:

①（这些是“代表”）;

②对任意,有（“代表”互不相同,尽管是允许的）.

定理1（Hall定理）对一族指标定义 .有限集族存在相异代表系,当且仅当下面的Hall条件（简记为HC）成立:

对任意 ,有.

证明：必要性显然，下面对用归纳法证充分性.

首先,定义指标族是临界的,若有相异代表系,且.于是,若是临界的,的每个元素都必须恰好是某一个的代表.空集和全集（如果是的话）,称为平凡的临界指标族.

当时,HC要求,从而可从中选出一个代表,集族存在相异代表系,即HC的充分性成立.

当时,假设充分性结论对成立,则对设满足HC,往证存在相异代表系,对是否存在非平凡的临界指标族,分下面两种情形考虑:

情形1 不存在非平凡的临界指标族.由HC知,不可能是空集.取中的一个元素.对,定义.注意到的任何子族是满足HC的.进一步,对的任意非空子集,有

（不临界）

.

从而集族满足HC,由归纳假设知,有相异代表系,不妨设为.由于

,

（注意）,

故就是集族的相异代表系.

情形2 存在非平凡的临界指标族.由于,并且易由满足HC知也满足HC,从而利用归纳假设知,有相异代表系.对,令.由于对任意与不交的指标族,都有

（是临界的）

,

故满足HC.由归纳假设知,可设的一个相异代表系是,那么它当然也是的一个相异代表系.由的定义知,从而是的一个相异代表系.

定义2（置换矩阵）每行每列都恰好有一个1其余均为0的-矩阵称为置换矩阵.

定理2设,若矩阵 满足为非负整数且其每行每列元素之和都为,则可以写成个置换矩阵之和.

证明：令 .取的任意子集.因的每列元素之和为,故在这些行上的元素总和为.因的每列元素之和也,故当限制在这些行上,每列（变短了的）上的元素之和不超过.由鸽笼原理知,总和为的在这些行上的非零元素分布在至少列上,此即HC：

所以存在的一个SDR.注意由的定有 ,且互不相等,即 分布在行列上.

令 这里,则 为一置换矩阵,并且

满足是非负整数,的每行每列元素之和都为.递归地,若,对于继续用上面的方法得到每行每列元素之和都是的及置换矩阵 ,使得

最后,从而

.

定理3 设为一个-矩阵,则包含中所有元素1的线（行或列）的条数的最小值（称为元素1的覆盖数）等于中两两不在一条线上的1的个数的最大值（称为元素1的匹配数）.

以上定理中提到的包含中所以元素的1的那些线称为一个覆盖,两两不在一条线上的1的集合称为匹配.该定理讲的是最小覆盖和最大匹配恰好为相同大小的数.

证明：显然.

下面设这个最小的覆盖中含有行,列,.我们构造一个含有个1的匹配.不妨设是前行,前列.对于,定义为.如果这些中的某个之并中少于个元素,则可用这些列（列）来代替对应的这行,仍然包含了所以的1,这与最小覆盖矛盾.所以满足HC,从而存在他们的一个SDR.这表示有个1,任何两个都不共线,这些1在前行但不在前列上.类似地,存在个1,任何两个都不共线,他们在前列但不在前行上.因此.

综合上述,知.

3 例题讲解

题例1 设为的所有,为的所有.求证：存在到的一个单射使得（对任意）.

证明：对,令,则.

问题等价于在中找出SDR,即为任意个元素之并（含有个元素）,对于每个,有 个 满足,每个元素最多出现21次,则中任意个元素之并至少含有个 元素,故满足Hall条件,存在SDR.即有且两两不同,则为所求的单射.故存在到的一个单射使得（对任意）.

剩余内容已隐藏，请支付后下载全文，论文总字数：5396字