【算法•日更•第四十六期】二分图（基础）

忘是亡心i 2023-06-03 02:52 2阅读 0赞

▎前言

小编昨天写了关于静态二叉排序树的建立，但是小编今天果断的不写静态二叉排序树的使用了，因为写了就感觉在专门水博客。

前段时间老师问我会不会二分图，小编才知道有这个东西，那么本篇博客就来讲一讲二分图的基础知识吧。

话说隔壁hza的二分图博客真的是接地气啊，呈上链接：[二分图博客][Link 1]。

▎什么是二分图？

☞『引入』

二分图二分图，一定是分成了两份的图是这个样子喽。

实际上还真的是分成了两份。

二分图将图（按点）分成了两个集合，处理的就是两个集合的点之间连边的问题。

☞『定义』

> 　　[二分图][Link 2]又称作二部图，是图论中的一种[特殊模型][Link 3]。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
> 
> 　　简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。（copy自百度）

说白了就是分成了两个互不相交的子集，连线的问题而已，形象一点长这样：

![1551435-20190818143540462-558499024.png][]

上图是小编随手一画的结果，小编也不确定是不是二分图，原因见二分图的判定。

个人认为二分图更像一种匹配用的东西，因为子集中的点不能互相连边。

另外，小编发现百度上的科普中国弄的视频感觉还不错，推荐大家看看：[链接][Link 4]。

☞『用途』

相信大家也有和我一样的问题，究竟这个东西能用来干什么？

这个东西主要是处理这样的问题：

> 　　给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配.
> 
> 选择这样的边数最大的子集称为图的最大匹配问题（maximal matching problem)
> 
> 如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

百度上说的过于真实，小编还是接地气的讲一遍这段话的意思吧。

就是说（在保证是二分图的情况下）任意两条边不能存在公共的顶点，形象一点说就是1 VS 1,这才公平，例如下图的红边间的关系：

![1551435-20190818150553065-215786594.png][]

只要是这样的红线，我们都称之为这个二分图的匹配。

我们问题中的最大匹配就是希望这样的红线尽可能的多。

▎二分图的判定

这个很好判定，众所周知，图是有环的，但是环的边数分为奇数和偶数，二分图是不含奇数条边的环的图。

转载于:https://www.cnblogs.com/TFLS-gzr/p/11372523.html

[Link 1]: https://www.cnblogs.com/Alan-Anders/p/11244728.html
[Link 2]: https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E5%9B%BE/9089095
[Link 3]: https://baike.baidu.com/item/%E7%89%B9%E6%AE%8A%E6%A8%A1%E5%9E%8B/19071206
[1551435-20190818143540462-558499024.png]: /images/20230601/cfb239b9d9ac41178db738a331e9da72.png
[Link 4]: https://baike.baidu.com/item/%E4%BA%8C%E5%88%86%E5%9B%BE/9089095?fr=aladdin
[1551435-20190818150553065-215786594.png]: /images/20230601/11dca97dca934006adf0bd346af2011a.png