霍尔婚姻定理的应用
霍尔婚姻定理在数学的不同领域的多种应用。我们将着眼于打造拉丁方，具有稳定的婚姻，并寻求高校录取的申请。
创建拉丁方
回想一下，拉丁方是一个 数组填充 不同的符号，其中每一个的每一行中的每一列恰好一次发生，并且正好一次。拉丁矩形是 数组 充满了 不同的符号，其中每个符号在每行最多出现一次，在每列最多出现一次。
假设我们有一个 顺序拉丁矩形 那么这个可以推广到an 拉丁方。
我们注意到，这足以表明我们可以将此扩展到 顺序拉丁矩形 从那时起，我们就可以归纳到an 拉丁方。
考虑用二分图 顶点, 在bipartition对应的左手侧到顶点 拉丁矩形的列，以及 右边的顶点对应于 拉丁矩形的符号。有在左顶点和上如果相应的列不包含对应符号右侧的顶点之间的边。注意，在这个图中的完美匹配对应于一个新行，我们可以添加到我们的拉丁矩形。
我们构造的图是a 普通二分图。我们将利用霍尔婚姻定理表明，任何 AN. -regular二部图拥有完善的配套。
考虑一组 大小 从bipartition的一侧的顶点。每个顶点有 邻居，所以边缘的总数从现身 是 在另一边的每个顶点有度 所以由鸽巢原理，至少有 邻居。因此，该图满足Hall条件，并具有所需的完美匹配。
稳定婚姻问题
稳定婚姻问题是与婚姻问题相关的问题。而不是每个顶点只在对边有一些邻居，它有一个对边所有顶点的有序排序。
假设我们有两组同等大小的人 和 这样，每个人都有在另一组人的有序列表。之间的匹配 和 被认为是稳定的，如果我们不能找到 和 这样 pref 的人，他们目前正在匹配和 pref 和他们现在匹配的人。
当Gale-Shapley算法是找到稳定婚姻的一种方法。算法如下:
１ ２ ３ ４ ５ |
|
要看到算法以完美匹配结束，观察一旦一个顶点进入 成为匹配，它永远不会成为无法比拟的。当算法终止，如果有在匹配顶点 那么它会提出匹配无可匹敌的顶点 而该提案已被接受。
要看匹配是否稳定，假设有 和 这是无与伦比的，并且每个喜欢对方。自从 pref 其目前的比赛， 一定要求婚吗 在某种程度上。自从 匹配比其他人 必须选择在这个比赛上 因此不能选择 其目前的比赛。
这方面的一个应用是与网络流量在互联网上处理。当在服务器上的大量处理大量的流量，你需要决定将流量发送到哪个服务器。交通的偏好一般都是成本，这可能是金钱和时间的关系，利用某些服务器相关联。该服务器的偏好一般是根据他们的沟通是多么可靠，这里的交通是始发。
大学入学问题
另一个相关的问题被称为高校自主招生问题．设想一组院校和一群学生。每个学生有兴趣参加一些高校和各高校有兴趣在接受一些学生，但每个也有偏好于哪些他们愿意接受。我们希望找到一个稳定的匹配分配学生到学校，以便有没有学生/大学对，其中学生宁愿去那个大学一个比他们要和学院宁愿有学生比其他一些一他们已经接受。
请注意，这是从稳定的婚姻问题略有不同，因为学生并不一定要到所有的学院和大学不希望接受所有的学生。
这个问题发生在现实世界中，当国家住院医师匹配计划试图将医科学生与医院进行住院医师匹配时。
附加题
1）（ 普特南B3)循环赛 团队历时 天，具体如下：在每一天，每一个团队在每个打了一个对阵另一支球队，一个球队获胜和一次输球 游戏。在比赛的过程中，每队每打其他球队一次。一个可以一定会选择从每天一个获胜的球队没有选择任何一支球队不止一次？
2）（ ISL C2）在某个星球上，有 国家 ）。每个国家都有一个标志 单位宽和单位高组成 尺寸的领域 每个字段不是黄色就是蓝色。没有两个国家的国旗是一样的。我们说一个集合 标志是多样的，如果这些标志可被布置成 平方，以便所有 其主对角线上的字段将具有相同的颜色。确定最小的正整数 在任何 有明显的标志 旗帜形成了一个不同的集合。
3）在一个 板，有 每行中乌鸦和板的各列。表明存在 属于不同的两两行和两两不同的列乌鸦。