×
<联系方式<
-全国统一服务热线-
0731-84812166
专业解决校区招生难问题
校区整体运营专家
邦栋教育专业解决培训机构招生难问题,提供全费招生服务,科培思维数学加盟,杨海蒂英语加盟,机器人培训加盟项目。
教育资讯

座位安排中体现的图论理论——匹配

在义务教育与高中阶段,几乎在每一学期初的时候,班主任都会重新安排全班同学的座位。一张桌子最多只能坐下一名同学,但也有可能出现空置的桌子。

在义务教育与高中阶段,几乎在每一学期初的时候,班主任都会重新安排全班同学的座位。一张桌子最多只能坐下一名同学,但也有可能出现空置的桌子。但由于受到现实条件(学生身高、个人意愿等)的影响,每个学生希望的座位方位是不同的,如何将每位学生都能安排在其希望的座位上成为一个值得讨论的问题。这是图论中匹配概念的一个原始模型,通常将有同学的桌子组成的这个调集称为匹配调集,将同学对应到桌子的进程就被称为匹配进程。


我们仍以座位安排为例做进一步的解说。将每位学生的希望座位列出一个表格,而且在表格的基础上作出二分图就是一种办法:


想要做到将每个学生都安排在其希望的座位上,需求每个学生都能匹配到互异的座位,即二分图中的线段(在匹配中称之为边)存在n个边,且这些边的端点互相不触摸的情况。也就是说存在一个边集E使得调集中的恣意两边不邻接,而且对每个结点bi而言,都能与调集E中边的左端点重合。这也就是所说的彻底匹配,笼统为概念就是二分图G(V1,V2)的彻底匹配,即存在单射f:V1→V2,使得恣意v=V1,且v与f(v)相邻。其间V1表明的是二分图左边的结点,而V2表明的是二分图右边的结点。通俗而言,关于排座问题,彻底匹配需求恣意n个同学至少需求希望n个座位方位。


那么假如在很难达到彻底匹配的实际情况中,如何分配可以使最多的学生都满足自己的座位呢?这儿就要引出最大匹配的概念了。匹配指的是关于无环图G来说,M∈E(G),且M≠?,假如M中恣意两条边在G中均不相连,就称M为G的一个匹配。也就是说匹配是将学生与座位可以一一对应的调集。匹配相关于彻底匹配而言,不同的条件在于不要求对每一个结点都有一个匹配联系,也就是说匹配不同于彻底匹配,有的学生在限制希望条件的前提下不会有分配的座位。那么最大匹配的意思是,最大匹配Mmax的元素数量要大于其他恣意匹配集的元素数。这个元素数也被叫做匹配数。


与匹配途径M有关的概念也有两种,一种是替换途径,指的是关于E(G)来说,每一条边替换地归于匹配途径M或者不归于M,比如第1、第3等奇数条途径归于M而第2、第4等偶数途径不归于M;另一种是增广途径,指的是从M中没有的起点开始到M中没有的终点结束,结合上文可以看出,当增广途径为空集时,M将成为彻底匹配。


日常生活中也存在更能凸显匹配概念的事例,比如工作分配问题,行将现有的个人与份工作进行匹配,使得每个人都可以得到自己擅长工作的匹配进程;比如运送问题,行将m座不同的矿山与运用矿山的n个工厂进行匹配,使得每个工厂都可以得到自己需求材料的矿山供货的进程等等。


来源: 新华网


精彩推荐
最新推荐
本月最热门
精彩推荐