霍尔婚姻定理的应用

霍尔婚姻定理在不同的数学领域有很多应用。我们将看看创造拉丁方块、拥有稳定的婚姻和申请大学入学的应用。

回忆一下拉丁方是一个 $N \乘N$数组中包含 $n$不同的符号，每一行恰好出现一次，每列恰好出现一次。拉丁矩形是an $M \乘以n$数组 $n$充满了 $n$不同的符号，其中每个符号在每一行最多出现一次，在每列最多出现一次。

假设我们有一个 $K \乘以n$拉丁有序矩形 $n。$然后这个可以扩展到an $N \乘N$拉丁方。 $_ \广场$

---

我们注意到，这足以证明我们可以将其扩展到a $(k+1) \乘以n$拉丁有序矩形 $n,$从那以后，我们可以归纳到 $N \乘N$拉丁方。

考虑一个二部图 $2 n$顶点 $n$双分区左侧的顶点对应于 $n$拉丁矩形的列，和 $n$右边的顶点对应于 $n$拉丁矩形符号。如果相应的列不包含相应的符号，则在左边的顶点和右边的顶点之间有一条边。观察一下，这个图中的完美匹配对应于我们可以添加到拉丁矩形中的新行。

我们构造的图是a $M = n-k$正则二部图。我们将用霍尔婚姻定理来证明 $米,$一个 $米$-正则二部图具有完美匹配。

考虑一组 $P$的大小 $p$来自双分区一侧的顶点。每个顶点都有 $米$邻居，也就是从哪里出来的边的总数 $P$是 $点。$另一边的每个顶点都有度数 $米,$根据鸽子洞原理，至少有 $\frac{pm}{m} = p$邻居。因此，该图满足霍尔条件，符合要求，具有完美匹配。 $_ \广场$

稳定婚姻问题是与婚姻问题相关的问题。而不是每个顶点只有一些邻居在对面，它有一个顺序排列的所有顶点在对面。

假设我们有两组身材相同的人 $一个$而且 $B$这样每一个人都有另一个人的有序列表。之间的匹配 $一个$而且 $B$如果我们找不到，就说它是稳定的 $a \in a$而且 $b \in b$这样 $一个$更喜欢 $b$和当前匹配的人 $b$更喜欢 $一个$和他们当前匹配的人。

的Gale-Shapley算法是找到稳定婚姻的一种方法。算法如下:

1 2 3 4 5

每个顶点开始时都不匹配。当集合A中有一个不匹配的顶点时，A中的每个不匹配的顶点都提议与它尚未尝试匹配的最首选的B顶点进行匹配，如果B顶点不匹配，那么这些顶点现在就匹配了，如果B顶点匹配，它选择建议的顶点或现有的匹配的首选顶点，另一个顶点保持或成为不匹配的顶点

为了看到算法以完美匹配结束，观察一个顶点 $B$是匹配的，而不是不匹配的。当算法终止时，如果有一个不匹配的顶点 $一个,$然后它会建议匹配一个不匹配的顶点 $B$这个提议应该会被接受。

为了确认匹配是否稳定，假设有 $a \in a$而且 $b \in b$它们是无与伦比的，而且彼此更喜欢对方。自 $一个$更喜欢 $b$对于当前的匹配， $一个$必须提出匹配 $b$在某种程度上。自 $b$被匹配到其他的人 $一个,$ $b$一定是选择了这场比赛 $一个$因此不能选择 $一个$到当前匹配。

它的一个应用是处理互联网上的网络流量。当处理大量服务器上的大量流量时，需要决定将流量发送到哪个服务器。流量的偏好通常是与使用特定服务器相关的成本，可能是金钱或时间相关的。服务器的首选项通常基于它们与流量起源地的通信的可靠性。

另一个相关的问题被称为大学录取问题．考虑一群大学和一群学生。每个学生都有兴趣进入一些学院，每个学院都有兴趣接收一些学生，但每个学院也有自己的偏好，他们想要接收哪些学生。我们希望找到一个稳定的配对，将学生分配到大学，这样就不会有学生/大学配对，学生宁愿去那所大学而不是他们将要去的那所大学，而学校宁愿要那个学生而不是他们已经录取的其他学生。

请注意，这与稳定的婚姻问题略有不同，因为学生不一定想上所有的大学，大学也不一定想录取所有的学生。

这个问题发生在现实世界中，当国家住院医师匹配计划试图将医科学生与住院医师医院进行匹配时。

1) ( $2012$的循环赛 $2 n$团队持续了 $2 n - 1$在每一天，每个队与另一个队进行一场比赛，每一场比赛一胜一负 $n$游戏。在整个比赛过程中，每支球队只与其他球队打过一次球。一个人是否可以每天只选择一个获胜的球队而不选择任何一支球队多于一次?

2) ( $2010$在某些星球上，有 $2 ^ N$国家 $N$)．每个国家都有一面国旗 $N$单位宽和单位高组成 $N$大小领域 $1 \乘以1，$每个字段要么是黄色要么是蓝色。没有两个国家的国旗是一样的。我们说一套 $N$旗帜是多样化的，如果这些旗帜可以安排成一个 $N \乘N$方形，所以 $N$主对角线上的字段将具有相同的颜色。确定最小的正整数 $米$这样一来，在任何 $米$明显的标志，存在 $N$形成不同集合的旗帜。

3)在…… $2n \乘以2n$董事会，有 $n$板子的每一行和每一列都有白嘴鸦。证明存在 $2 n$属于成对不同行和成对不同列的白嘴鸦。