二分图

中国如今男女比例严重失衡，2021年预计将有9200万单身贵族。为了帮助解决这个社会性问题，提升整体人民的幸福感，小K打算投身到这份伟大的事业中。 “ 几何思维 ”婚恋所，用最科学的方法，帮你脱单。通过概率论寻找最佳匹配对象，再通过微积分精确计算好感上升曲线，最后用数值分析无限逼近对方的理想型。最可怕的是，还包邮呢亲，关注一波了解一下？ 上班第一天，老板给了小K一份单身男女好感的数据资料。如下图，连线表示双方互有好感，可以尝试处对象。 突然遇到了一个问题，那怎么才能进行最大的匹配，创造整体人民最大的幸福感呢，当然也可以顺便拿最多的中介费啦。 很多时候不是你比别人差，而是你执行力不够，在犹豫中丧失机会。 大家就先行动起来吧。 快看，男1号选手在小K的鼓励(怂恿)下，率先对女1号发起了进攻。在离失败只有0.01公分的时候，他竟然奇迹般的完成反杀，没错，他成功啦，这种高超的技巧，娴熟的手法简直如同教科书一般，值得在座的每个同学深入研究反复琢磨啊。 男2号选手也不甘落后，也对女2号选手发起了进攻，没错，又一次成功啦。 男3号选手：我勒个去，我上我也行啊。于是也对自己心动的女1号发起了进攻，毫无意外，他阵亡了。。。 中间彩蛋。 男3号不甘心，原地复活，想再战一回。在一个地方跌倒，咱们就换一个地方再跌。。。 于是对女2号发起了进攻。 几经波折。 男3号终于也成为了有牵绊的男人，不论未来有多久，只在乎曾经拥有过。 男4一看：这也没我啥事儿了啊。 以上的过程其实就是经典的 匈牙利算法 ，求解二分图的最大匹配问题。 二分图 定义：设G=(V,E)是一个无向图，顶点集V可分割为两个互不相交的子集X，Y，并且图中每条边关联的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。 判断是否为二分图的充要条件：G至少有两个顶点,且其所有回路的长度均为偶数。 判断方法：染色法 可用bfs或者dfs。 匹配 在二分图G的子图M中，M的边集E中的任意两条边都不依附于同一个顶点，则称M是一个 匹配 。 饱和点 匹配M的边集所关联的点为 饱和点 ，否则为 非饱和点 。如上图： 交错路 定义：图G的一条路径，且路径中的边在属于M和不属于M中交替出现。 增广路(非网络流中的定义) 定义：一条交错路，且该交错路的起点和终点都为匹配M的非饱和点。 如上图，交错路1是增广路；交错路2不是增广路，因为终点 X1 不是非饱和点。 由增广路推出以下结论： 匈牙利算法核心思想： 变量定义及初始化 初始化 递归寻找增广路 遍历所有点 测试数据

汉密尔顿图　　汉密尔顿图　　与欧拉回路非常类似的问题是汉密尔顿回路的问题。　　1859年，威廉·汉密尔顿爵士在给他朋友的一封信中，首先谈到关于十二面体的一个数学游戏：能不能在图中找到一条回路，使它含有这个图的所有结点？（见图）　　他把每个结点看成一个城市，联结两个结点的边看成是交通线。于是他的问题就是能不能找到旅行路线，沿着交通线经过每个城市恰好一次，再回到原来的出发地，他把这个问题称为周游世界问题。　　定义1给定图g，若存在一条路经过图中的每个结点恰好一次，这条路称作汉密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。　　具有汉密尔顿回路的图称作汉密尔顿图。　　定理1若图g=具有汉密尔顿回路，则对于结点集v的每个非空子集s均有w(g-s)≤|s|成立。其中w(g-s)是g-s中连通分支数。　　定理2设g具有n个结点的简单图，如果g中每一对结点度数之和大于等于n-1，则在g中存在一条汉密尔顿路。　　定理3设g是具有n个结点的简单图。如果g中每一对结点度数之和大于等于n,则在g中存在一条汉密尔顿回路。　　定义2给定图g=有n个结点，若将图g中度数之和至少是n的非邻接结点连接起来得图g"，对图g"重复上述步骤，直到不再有这样的结点对存在为止，所得到的图，称为是原图g的闭包，记作c(g)。　　定理4当且仅当一个简单图的闭包是汉密尔顿图时，这个简单图是汉密尔顿图。