匹配(图论)
在图论,一个匹配在一个图是一组没有公共顶点集的边。换句话说,匹配是一个图,其中每个节点都有零条或一条边与之关联。
不要与图匹配混淆图的同构.图同构检查两个图是否相同,而匹配是图的特定子图。
图匹配在流网络,调度和规划、建模债券在化学、图着色,稳定的婚姻问题,神经网络在人工智能和更多。
许多图像匹配算法存在是为了优化手头问题所要求的必要参数。
假设有一组候选人和一组工作,每个候选人至少有资格胜任其中的一个工作。我们可以使用图表匹配来看看是否有办法给每个候选人一份他们符合条件的工作。下面的图表显示了所有的候选人和工作,候选人和他们能胜任的工作之间有一个优势。
有没有一种方法可以把每个人分配到一个他们有资格的工作上,使每个工作只分配给一个人?
是的,有一种方法可以将每个人分配到单一的工作,即为每个工人匹配指定的工作。虽然这个问题的解决方案可以快速解决,没有任何效率算法,随着节点数量的增加,例如在社交网络中,这类问题会变得相当复杂。
定义和术语
匹配
给定一个图 ,一个匹配是一个子图的 , ,其中每个节点的度数不超过1。匹配由不共享节点的边组成。
最大匹配
一个匹配的, 的图, ,据说是最大如果没有其他边 可以添加到 因为每个节点都与另一个节点相匹配。换句话说,如果一条边在 并且不在 被添加到 ,它会导致 不再是一个匹配图,因为一个节点将有多个边与它相连。 如果不是,也是极大匹配真子集任何其他匹配的 ;如果每条边 有一个至少有一条边的非空交集 [3].注意,最大匹配不一定是提供图中可能的最大匹配数的子图。
最大匹配
匹配是A最大匹配如果它是一个包含最大可能数量的边匹配尽可能多的节点的匹配。简单地说,最大匹配是最大匹配最大的边数。每个最大匹配都是最大匹配,但并不是每个最大匹配都是最大匹配。
在加权图,有时找到一个使权重最大化的匹配是有用的。
一群学生正被安排成搭档参加一个科学项目。每个学生都确定了自己对伴侣的偏好列表,用代表偏好的数字对每个同学进行排名,最好的朋友的排名最高为20,因为一共有21名学生,所以不能重复排名。老师决定将这个问题建模为一个图,方法是在每个学生之间划出一条边,并为每条边分配一个权重,该权重等于每个学生对彼此排名的平均值。老师意识到,为了最大化班级的整体幸福感,她必须找到整个班级的最大匹配。
最小重量的匹配如果最大匹配的目的是最小化图的总体权重,也可以执行;如果上面例子中的老师让学生把他们最好的朋友按升序排列。
如果用不同的边子集获得相同的最大权值,则图可以包含多个最大匹配。图中最大匹配的大小或总权重称为匹配的数量.
完美的匹配
一个完美的匹配是一个匹配,其中每个顶点只与一条边相连;其中匹配匹配图中的所有顶点。在一个非加权图中,每一个完美匹配都是a最大匹配因此,是最大匹配也如果图是加权的,则可以有许多不同匹配数的完美匹配。从形式上讲,是一个图的匹配 如果它是完美的 边缘。
一个近乎完美的匹配,在另一方面,可以发生在具有奇数个顶点的图中。在这种情况下,很明显,如上所述的完美匹配是不可能的,因为会留下一个节点不匹配。这种情况还会导致节点数为奇数的图的最大匹配。
双方的匹配
为了更清楚地建模匹配问题,通常将图转换为两偶图,它的顶点集被分为两个不相交的集合, 而且 ,在那里 所有的边都连接了顶点 而且 .
在上面的二部图中找到一个匹配的图。
图中有一个可能的匹配。另一种匹配可能会出现——记住,它是任何子图,其中子图中的每个顶点只有一条边。这是一个近乎完美的匹配,因为只有一个顶点不包含在匹配中,但记住,匹配是一个图的任何子图,其中子图中的任何节点都有一条边从它出来。
配对问题的例子
匹配过程通常用于回答与图相关的问题,例如顶点覆盖,或网络,如流或社交网络;这类问题中最著名的是稳定的婚姻问题.
稳定的婚姻问题
稳定婚姻问题的目的是促进两组人之间的配对。给定一个潜在配偶的列表,在相同数量的新娘和新郎中,稳定婚姻问题在这个列表上给出了一个充要条件,使每个人都能与称心如意的配偶结婚。这个定理可以应用到任何情况下,两个顶点必须匹配在一起,以最大化效用,或整体幸福。
有 礼物标签 )在圣诞树下,和 收到礼物的孩子有:爱丽丝、鲍勃、查尔斯、丹妮尔和爱德华。能不能把礼物分配给每个人,这样每个人都能得到自己喜欢的礼物?
如果他们中没有人喜欢礼物,那么解决方案可能是不可能的,没有人会喜欢他们的礼物。即使存在轻微的偏好,如果没有人喜欢礼物,分配也会相当困难 或 ,则只 礼物将会分发给 的孩子。在另一种情况下,假设
爱丽丝想要礼物1 3。
鲍勃想要2 4 5 6的礼物。
查尔斯想要礼物2 3
Dot想要礼物1 2 3。
爱德华想要礼物。
仍然没有办法分配礼物让每个人都高兴。事实上,请注意,其中四个孩子,爱丽丝、查尔斯、丹妮尔和爱德华,只想要前三份礼物中的一份,这表明问题是不可能的,其中一个将被困在一份他们不喜欢的礼物中。
然而事实证明,这是只有这个问题不可能解决。只要没有一个子集的孩子,他们喜欢的礼物比这个子集的孩子总数少,就总有办法给每个人他们想要的东西。这就是霍尔婚姻定理的关键。
这只是这个问题的一个简要概述。有关霍尔稳定婚姻定理的更多信息,请参阅稳定的婚姻页面和稳定婚姻定理的应用页面。
顶点覆盖
顶点覆盖,有时称为节点覆盖,是一个使用匹配的著名优化问题。对于一个图 ,顶点覆盖是一组顶点 这样图中的每条边都至少有一个端点在 .下面是两个图,它们的顶点覆盖集用红色表示。基本上,顶点覆盖“覆盖”了所有的边。
艺术博物馆里满是名画,所以安保必须无懈可击。确保没有人能偷走这些昂贵的艺术品是至关重要的,所以安保人员必须安装安全摄像头来密切监视每一幅画。为了确定在走廊的哪个位置放置这些摄像头,以便所有的画作都受到保护,保安可以查看博物馆的地图,并将其建模为一个图形,其中走廊是边缘,角落是节点。如果在一个没有转弯的走廊里,有五幅画沿着一面墙排列,那么大厅开头的一个摄像头将守卫所有五幅画。这样,安全人员可以确定顶点覆盖集,以找到放置摄像机的位置。
为了进一步改进摄像头的放置,安保人员可以通过实现一种称为最小顶点覆盖.
关于顶点覆盖的一个更理论化的概念是柯尼希定理这说明对于任何两偶图,匹配的最大大小等于顶点覆盖的最小大小。
交通理论
匹配算法在资源分配问题中也有巨大的应用流网络问题。在数学和经济学中,对出行中的资源配置和优化的研究被称为交通理论.[9]
在大城市里, 工厂生产电脑和 商店出售电脑。每个工厂只能向一个商店运送电脑,而每个商店只能从一个工厂接收货物。如果工厂的位置是 商店的位置是 ,然后是运输计算机的成本 来 可以通过计算机与商店之间的匹配来建模, .最优运输计划确保每个工厂恰好供应一个商店,而每个商店恰好由一个工厂供应,从而使计算机从工厂到商店的运输总成本最小化。这个问题等价于在二部图中寻找最小权值匹配。这个图是二部的,因为有 工厂和 商店和商店和工厂之间的加权边是在这些节点之间移动计算机的成本。
另请参阅
参考文献
- , R。匹配(图论).检索于2016年6月19日https://commons.wikimedia.org/wiki/File Matching_ (graph_theory) . jpg
- ,我。具有匹配的二部图.检索于2016年6月19日https://commons.wikimedia.org/wiki/File:Bipartite_graph_with_matching.svg
- , .匹配(图论).检索于2016年6月18日https://en.wikipedia.org/wiki/Matching_ (graph_theory)
- , M。Maximal-matching.svg.检索于2016年6月18日https://en.wikipedia.org/wiki/File:Maximal-matching.svg
- , M。Maximum-matching-labels.svg.检索于2016年6月18日https://en.wikipedia.org/wiki/File:Maximum-matching-labels.svg
- , M。Simple-bipartite-graph.svg.检索于2016年6月18日https://en.wikipedia.org/wiki/File:Simple-bipartite-graph.svg
- , M。Vertex-cover.svg.检索于2016年6月25日https://en.wikipedia.org/wiki/File:Vertex-cover.svg
- D。Triangulation_3-coloring.svg.检索于2016年6月25日https://en.wikipedia.org/wiki/File:Triangulation_3-coloring.svg
- , .运输理论(数学).检索于2016年6月24日https://en.wikipedia.org/wiki/Transportation_theory_(数学)