图论2 江川.

Presentation on theme: "图论2 江川."— Presentation transcript:

1 图论2 江川

2 二分图 一个图的点集可以划分为两个不相交的子集，每一个子集中的点和该子集中的其他点没有边相连

3 二分图 一个图是二分图的充要条件是这个图里没有奇环

4 二分图匹配 匹配：给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
最大匹配：所有匹配中边数最多的。 完备匹配：如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完备匹配。

5 二分图匹配

6 Hall定理 一个二分图有完备匹配的充要条件是： 任意k个点相邻的点的集合中不少于k个点

7 匈牙利算法 M-交错路：p是G的一条通路，如果p中的边为属于M中的边与不属于M的边交替出现，则称p是一条M-交错路。
M-饱和点：对于v∈V(G），如果v与M中的某条边关联，则称v是M-饱和点，否则称v是非M-饱和点。 M-可增广路：p是一条M-交错路，如果p的起点和终点都是非M-饱和点，则称p为M-可增广路。

8 匈牙利算法

9 匈牙利算法 For all i in X: 1、从i出发寻找可增广路 2、沿增广路更新 （删除原属于M的边，增加不属于M的边） O(nm)

10 匈牙利算法

11 匈牙利算法

12 匈牙利算法

13 应用1 点覆盖集：图的顶点集的子集，覆盖图中所有的边 最小点覆盖：无向图中，求最少需要多少个点可以覆盖所有的边。 NP

14 应用1 二分图的最小点覆盖

15 应用1 König定理： 二分图的最小点覆盖 = 最大匹配

16 应用1 假设最小点覆盖=N，最大匹配=M 考虑最大匹配中的边两两不相交，所以至少需要M条边覆盖。 得N>=M

17 应用2 独立集: 图的顶点集的子集，其中任意两点不相邻。 最大点独立集: 无向图中，求一个最大的顶点集，其中任意两点不相邻。 NP

18 应用2 覆盖集的补集一定是独立集 证明： 假设某一覆盖集的补集不是独立集。说明有一条边连接了覆盖集的补集的两个点。那么这条边没有被覆盖集所覆盖，产生矛盾。

19 应用2 独立集的补集一定是覆盖集 证明： 假设某一独立集的补集不是覆盖集。说明有一条边不被独立集的补集覆盖，那么这条边连接了独立集的两个端点，产生矛盾。

20 应用2 覆盖集与独立集互为补集 二分图中可求出最大匹配M 最小覆盖集=M，最大独立集=n-M

21 应用3 一共N个男孩和女孩参加聚会，某些男孩和女孩之间会产生恋爱关系。现在希望找到最多的孩子，他们之间不会产生恋爱关系。

22 应用3 男孩在一边，女孩在一边 会产生恋爱关系的连边 找最大独立集

23 应用4 一共N个人参加聚会，某些人之间会产生恋爱关系（一定是异性之间）。现在希望找到最多的人，他们之间不会产生恋爱关系。

24 应用4 所有的人复制成两份放在两边 会产生恋爱关系的连边 最大独立集 = N – 最大匹配 / 2

25 应用5 给你一个N*N的格子，每个格子里要么有一个陨石，要么为空。每一次你可以清除一行或者一列里的所有陨石，求最少要多少次才能把所有的陨石清除干净。 X

26 应用5 把N*N的格子看成是一个二分图，每一行是一个集合的点，每一列是另一个集合的点，那么某个格子（x,y）中有陨石就相当于顶点x到顶点y有一条边，那么要求使陨石全部被清理掉的最少的次数，就是要使该二分图中的所有边都被覆盖的最少顶点数。 X

27 应用6 动物园有N只猫，M只狗，P个小孩。每个小孩都有自己喜欢的和讨厌的动物。如果他喜欢狗，那么就讨厌猫；如果他讨厌猫，那么他就喜欢狗。每个小孩会说，我喜欢__号猫，讨厌__号狗；或者说，我喜欢__号狗，讨厌__号猫。如果他喜欢的那只动物被留下，而且讨厌的那只动物被带走，他就会开心。请问最多有多少小孩能开心。

28 应用6 现在要求最多的小孩，两两之间不矛盾 从矛盾关系入手 猫和猫之间，狗和狗之间一定不存在矛盾关系
如果A小孩喜欢的动物与B小孩讨厌的动物一样，或者A小孩讨厌的动物与B小孩喜欢的动物一样，那AB之间就存在着排斥关系，则他们之间连接一条边（他们不可能同时开心） 求最大的点集，两两之间没有边 最大点独立集

29 应用7 路径覆盖：路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联 。注意一个单独的点也是一条路径。 现要求有向无环图的最小路径覆盖，即在一张有向无环图中，找路径数最少的路径覆盖。

30 应用7 把每个顶点拆成两份，然后按原图连边。

31 应用7 最小路径覆盖 = n – 最大匹配 每一个匹配相当于原图中的某两个路径合并

32 应用8 在一个有向无环图上，至少放多少个机器人可以遍历整个图？ 注意点是可以重复经过的。

33 应用8 允许重复经过点的最小路径覆盖 如果经过一个重复的点我们可以假装跳过了它进入下一个点 Floyed求出传递闭包再做最小路径覆盖

34 应用9 在一个N*M的矩形里，有一些格子被毁坏。现在要求用1*2的木板去覆盖没有被毁坏的格子，木板不可覆盖彼此，问是否能把每个格子都盖住。

35 应用9 所有没有被毁坏的格子都看成图中的点 按格子的“奇偶性”分成两类 如果两个格子相邻，则在这两个点上连边
若存在完备匹配则所有的格子可以被覆盖

36 应用10 A机器有n个模式，B机器有m个模式。 现有k个任务需要做，可以用A机器的某个模式做或者用B机器的某个模式做。 任务不分先后，但是机器换模式需要重启。现在求最少的重启次数。

37 应用10 任务不分先后相同模式的连续做 用的模式越少越好最少的模式完成所有任务 把模式看成点，A的模式放在一侧，B的模式放在一侧。
对于某个任务，在它所要求的两个模式之间连边。 最小点覆盖集

38 二分图最佳匹配 最佳匹配：如果G为加权二分图，则权值和最大的完备匹配称为最佳匹配。

39 KM算法 KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。
设顶点Xi的顶标为A[i]，Yi的顶标为B[i]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，要求对于任一条边(i,j)，A[i]+B[j]>=w[i,j]始终成立。

40 KM算法 A[i]+B[j]>=w[i,j]

41 KM算法 若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。

42 KM算法 证明： 对所有的边有：A[i]+B[j]>=w[i,j]
对于二分图的任意一个完备匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。

43 KM算法

44 KM算法 设置初始顶标 寻找当前相等子图的完备匹配： 1、找到则结束。 2、未找到则修改顶标再重新寻找。

45 KM算法 初始顶标： 令A[i]为所有与顶点Xi关联的边的最大权，令B[j]=0。

46 KM算法 修改顶标： 找不到完备匹配 对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。
我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d

47 KM算法

48 KM算法 两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。

49 KM算法 两端都不在交错树中的边(i,j)，A[i]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。

50 KM算法 X端不在交错树中，Y端在交错树中的边(i,j)，它的A[i]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。

51 KM算法 X端在交错树中，Y端不在交错树中的边(i,j)，它的A[i]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。

52 KM算法 求d值？ 1、A[i]+B[j]>=w[i,j]始终成立 2、至少一条边进入相等子图
d = min{A[i]+B[j]-w[i,j]} 其中Xi在交错树中，Yi不在交错树中。

53 KM算法 d = 1

54 KM算法 KM算法求出的最佳匹配一定是完备匹配 因为最佳匹配的边权和等于顶标和

55 KM算法 求非完备匹配的最佳匹配？ 最小费用最大流

56 应用1 求权值和最小的完备匹配？

57 应用1 求权值和最小的完备匹配？ 边取负数（常用做法）

58 应用2 图中m表示人，H表示房子。现在要让所有人都走到一个房子里，且不能有两个人进入同一个房子。问所有人总共最少要走多少步。
mmmHmmmm

59 应用2 把每个m和H的距离算出 每个人看成一侧的点 每个房子看成一侧的点 每个人和每个房子连边，边权为距离 求最佳匹配
mmmHmmmm

60 谢谢！