有向无环图的最小路径覆盖问题

Posted on 2011-04-05 16:04 Mato_No1 阅读(2057) 评论(0)  编辑 收藏 引用 所属分类: 图算法
有向无环图的最小路径覆盖问题包括两种(设G是一个有向无环图,S是G的一个路径集合):
(1)最小点路径覆盖:满足对于G中所有的点i,i在S中的一条路径中出现,且只在S中的一条路径中出现,求S的最小容量;
(2)最小边路径覆盖:满足对于G中所有的边E,E在S中的一条路径中出现,且只在S中的一条路径中出现,求S的最小容量;

(1)最小点路径覆盖:
建立一个新图,将G中的每个点i在新图中拆成两个点i'、i'',若G中存在边<i, j>则在新图中连边<i', j''>,显然新图是一个二分图,求其最大匹配,则(N-新图最大匹配的值)就是最小点路径覆盖值。
时间复杂度:O(NM)(Hungary算法)

(2)最小边路径覆盖:
对于图中的每个点i,设D[i]为(i的入度-i的出度)的值,按照D[i]将图中的点分类:D[i]<0的称为“入少出多”的点,D[i]>0的称为“出少入多”的点,D[i]=0的称为“入出相等”的点。则有:
定理 有向无环图中最小边路径覆盖的值等于图中所有“入少出多”的点的D值之和。
证明:
其实只需证明:对于一个至少有一条边的有向无环图,必然存在一条路径,其起点是“入少出多”的点,终点是“出少入多”的点,所有中间点都是“入出相等”的点(只要不断的在图中找到并删去这条路径,直到图中无边为止)。
首先,由于图中无环,一定存在“入少出多”的点和“出少入多”的点。
然后,假设图中所有“入少出多”的点的后继(注意:后继和后代是不同的,一个点的后代包括这个点的所有后继、所有后继的后继、所有后继的后继的后继……)也都是“入少出多”的点,则图中所有“入少出多”的点构成了一个闭合子图,在这个闭合子图中,由于所有的点都是“入少出多”的,整个子图的入度之和必然大于出度之和,这是不可能的(有向图中的所有点入度之和必然等于所有点出度之和),故可得:图中必然存在至少一个“入少出多”的点,它有不是“入少出多”的后继。
这样,在这些拥有不是“入少出多”的后继的点中选择一个点i,将其作为路径的起点,在它的不是“入少出多”的后继中选出一个点j,若j是“出少入多”的点,则边<i, j>就是符合条件的一条路径,结束;若这样的j都是“入出相等”的点,则考虑j的后代:j的后继可能都是“入少出多”的,但j的后代中必然存在至少一个点j'不是“入少出多”的(否则j的所有后代也将构成全都是“入少出多”的闭合子图),这些j'中必然存在一个点的前趋i'是“入少出多”的,这是,需要舍弃原来的路径,将i'作为新路径的起点,j'作为新路径的第一个中间点,继续找;若j的后继不全是“入少出多”的,则若其中有“出少入多”的则路径已找到,若都是“入出相等”的,由于图中无环,将路径不断延伸,最终一定会找到合法路径。

由此可得,对于任何有向无环图,这样的路径都是存在的,也就证明了一开始的求最小边路径覆盖值的定理。
求有向无环图最小边路径覆盖值的时间复杂度:O(M+N)。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理