Skip to content

《组合数学》缩写(五)

第9章

这一章讲二分图中的匹配。给出了几个能启发思路的转化成二分匹配的模型:有禁止的棋盘上放非攻击车;有禁止的棋盘上放1×2骨牌;m个具有一定资格的人申请n个工作。将问题转化为二分图匹配模型的关键点是构造二分图,使可行解与合法的匹配一一对应,这样最优解一般就对应了最大匹配。

定义二分图的交错路径是这样一种路径:含有奇数条边,其中仅有第1条、第3条、……、最后一条边都没有包含在当前的匹配方案里,仅有路径的两个端点没有被匹配。一个匹配是最大匹配当且仅当不存在交错路径。求最大匹配的方法就是不断寻找交错路径并将使用其中的奇数边重建当前匹配方案的,这就是Hungary算法。书中给出的伪代码垃圾了,本来不用那么麻烦的,更好的代码参见我以前关于Hungary算法的文章

二分图的最小覆盖的意思是这样的:选定一些点,让所有的边都有端点被选择,选的点数尽量少。König定理是这样的:二分图的最大匹配数等于最小覆盖数。这个定理可以帮助解决另一类可以转化为二分图匹配模型(先转化为最小覆盖模型)的问题。

一个和二分匹配有关的问题叫稳定婚姻系统。似乎在OI中用途不太大(主要是不太具扩展性),问题和算法(延迟认可算法)我不描述了。

(第10章暂略)

第11章

图就是由顶点和边构成的东西,(无向或有向的)边可以认为是顶点中的一种(可交换或不可交换的)关系。顶点的度就是邻接的边的数量,如果是有向图的话还可以定义入度和出度。

欧拉路就是一条经过了所有边仅一次的(不一定是简单)路径。存在欧拉路的充要条件是有0个或2个度为奇数的顶点,前者的欧拉路的起点与终点是闭合的。欧拉路可以用圈套圈算法来求。不过书中的方法实现起来还是麻烦(需要写链表),有更好的方法。中国邮递员问题,就是求一条从一个点出发经过每一条边再回到起点的最短路径。解决这问题的大概想法就是通过添边把所有奇度顶点变偶。问题的算法书上没写,不过我想大约就是:找出所有奇度顶点求它们两两的最短路,然后求(非二分图的……)最优匹配。如果是有向的反而简单的多,因为这样可以根据负点和正点构造出二分图匹配。

Hamilton路径的定义就是一条经过所有顶点仅一次的路径。这是NP-Complete问题,目前没有多项式算法。

判断图是否是二分图只需要试图给图2涂色,如果涂出矛盾了就不是。

树是一种图,它的定义包括:任两点都有且仅有一条路径的图;不含圈的图;n个顶点n-1条边的连通图。

Shannon开关游戏很有意思。正方必胜策略的有无取决于图是否存在两个不存在重复边的生成树,如果找出了这两个生成树,必胜策略的算法还是不太复杂的。不过这两个生成树怎么找呢?

求最短距离树,其实就是求单源最短路径,所有的最短路径(可以)是一棵源点为根的树,用Dijkstra算法求。最小权生成数用Kruskal算法或Prim算法求。

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*