大家好，欢迎来到IT知识分享网。
2022开篇小论文，今天收到金博的来电，负责一个威胁检测的研究，对于这种名利双收的好事，自然是无法拒绝的，差不多30分钟的交流，基本上掌握了大概的检测思路，一上来就是没听过的二分图[1]，好在我热爱学习，差不多算是新瓶装旧酒，但是却有难度，然后丢下59篇英文论文说是研究研究~
二分图是什么？节点由两个集合组成，且两个集合内部没有边的图。U是一个集合，V是一个集合，U和V长的这么像，很容易眼花，搞不明白数学家为啥这样定义。二分图不存在长度为奇数的环，因为每一条边都是从一个集合走到另一个集合，只有走偶数次才可能回到同一个集合~
二部图
看上去很好理解嘛，然后我搜了一下二分图的最大匹配、完美匹配和匈牙利算法[2]，在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配
完美匹配：一个图的某个匹配中，所有的顶点都是匹配点
这里引出一个小故事，男孩女孩二分图，是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢呢？这就是完美匹配问题。如果换一个说法：最多有多少互相喜欢的男孩/女孩可以配对儿？这就是最大匹配问题。求解最大匹配问题的一个算法是匈牙利算法~
男孩女孩二分图
匈牙利算法思想[3]：通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时，达到最大匹配（增广路定理）。
为了理解这个思想，不得不掌握2个重要概念：
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。
增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路。
为了掌握这2个重要概念，又不得不掌握4个概念：
匹配的4个概念
在图3和图4中，红线是某个匹配，我们得到如下信息：
|
图3 |
图4 |
|
|
匹配点 |
1,5,4,7 |
1,2,3,4,5,6,7,8 |
|
匹配边 |
（1,5），（4,7） |
（1,7），（2,5），（3,6），（4,8） |
|
未匹配点 |
2,3,6,8 |
无 |
|
未匹配边 |
（1,7），（2,5），（3,5），（3,6），（4,8） |
（1,5），（3,5），（4,7） |
这个时候就很好理解了，所谓的交替路，就是“黑线-红线-黑线-红线”，增广路就是交替路的一部分，从一个未匹配点，走到另一个未匹配点，中间全是匹配点。
|
交替路 |
增广路 |
|
|
图3（匹配点：1,4,5,7） |
8->4->7->1->5->2 |
8->4->7->1->5->2 |
|
图4（匹配点：1,2,3,4,5,6,7,8） |
8->4->7->1->5->2 |
无 |
增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是增大匹配。只要把增广路中的匹配边和非匹配边的身份交换，增广路里面的红线变黑线，黑线变红线，就能从图3变成图4。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。
对调增广路里面的红线和黑线
增广路 |
匹配边 |
非匹配边 |
|
图3 |
（1,5），（4,7） |
（8,4），（7,1），（5,2） |
|
图4 |
（8,4），（7,1），（5,2） |
（1,5），（4,7） |
这时候就明白增广路原理了，就是不停的找增广路，增多匹配边和匹配点，找不到增广路时，达到最大匹配，匈牙利算法就是这么实现的。
参考
- ^二分图概述 https://oi-wiki.org/graph/bi-graph/
- ^二分图算法 https://www.renfei.org/blog/bipartite-matching.html
- ^匈牙利算法思想 https://blog.csdn.net/_/article/details/
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/97529.html
