图论的基本思想及方法.ppt
《图论的基本思想及方法.ppt》由会员分享,可在线阅读,更多相关《图论的基本思想及方法.ppt(44页珍藏版)》请在三一文库上搜索。
1、图论的基本思想及方法,湖南省长郡中学 任恺,由一道题目浅谈,概述,信息学中的图论问题层出不穷,变化多端,惟有掌握其基本思想和方法,才能以不变应万变!,下面通过实例主要从两方面论述图论的基本思想:,一、合理选择图论模型,二、充分挖掘和利用图的性质,雪山上有一个滑雪场。滑雪场由平台和滑道组成。每个平台有不同的高度,有一个最高点和一个最低点。滑道连接着两个不同的平台,方向是从较高点到较低点。,一些工人要检查滑道。每个工人从最高点滑到最低点,滑行路径上的滑道便都被检查了。每个工人只能滑行一次。不同工人的滑行路径可以有相同的滑道。,例题:滑雪者(POI 2002),问题:最少要多少个工人才能检查完所有的
2、滑道呢?,Nar.in 6 2 2 3 2 3 4 2 4 5 1 6 2 4 6,Nar.out 4,顶点个数n (1n5000),从左到右描述第i个顶点发出边的另一个端点,例题:滑雪者(POI 2002),1,2,3,4,5,6,选择模型(1)网络流模型,最高点 最低点 每条滑道可以多次通过 每条滑道必须被检查 有向无环图,网络的源点 s,网络的汇点 t,边下界 l 为1,边上界 u 为,分析样例,发现问题中有如下关键点:,很容易想到建立一个网络流模型:,最高点,最低点,s,t,确定所求目标,建立模型后,可以确定要求的目标:,求图G中一个最小可行流,满足:,s,t,2,1,3,1,2,2,
3、1,1,1,a) 每条边的流量大于等于下界,b) 从源点流出的总流量最小,求最小流的方法,如何求图G的最小流呢,求最小流可以分成两步:,1)求出图G上的可行流 f,2)将可行流 f 转化成最小流,对于有上下界的网络,通常用构造附加网络的方法求可行流。,但是观察图G可以发现,边的上界都是无穷大,也就是说没有流量上限。,ui,j = ,因此可以利用这个性质构造可行流,求可行流的方法,j,i,s,t,求可行流的方法,枚举每条流量为0的边,设为(i, j),任意找到一条从 s 到 i 的路径和一条从 j 到 t 的路径,那么s i j t 便是一条可行的流,将这条路径上的边流量加1, 便满足了边(i,
4、 j)的容量下界,fi,j = 0,fi,j = 1,+1,+1,f 可行,求最小流,设用上法求出的可行流的总流量为F,这个可行流可能“过剩”。,因此要将多余的流从汇点“退回”到源点。,f 最小,求最小流,s,在新图中,原图G的边(i, j)拆成两条边:,边(i, j), ui,j = fi,j li,j,li,j = 0,边(j, i), uj,i = ui,j fi,j,lj,i = 0,回退“过剩”流量可以用如下方法:,求最小流,在新图中,从 t 到 s 求出一个最大流,令这个最大流的总流量为F。,s,可得图G的最小流的流量为F F。,算法一的复杂度,易知构造可行流的时间复杂度为O(nm
5、),修改可行流所用的最大流算法时间复杂度为O(mC),其中C为增广的次数。,由于图G是平面图,所以边数是O(n)级别。而由可行流构造方法可知,增广次数C也是O(n)级别。,总的复杂度为O(n2),是否存在效率更高的算法?,选择模型(2)另辟蹊径的偏序集,下面介绍的偏序集模型将更好的解决此问题。,算法一能够很迅速的解决原题数据。,但当n的范围扩大时,算法一便无能为力了。,偏序集的定义,偏序集是一个集合P和一个偏序关系 ,满足下列性质:,自反性: 所有xP,都有x x。,反对称性: 所有x,yP,若x y且y x,则x = y。,传递性: 所有x,y,z P,若x y且y z,则x z。,链:链是
6、P的一个子集C,在偏序关系下,它的每一对元素都是可比的。,偏序集的相关概念,反链:反链是P的一个子集A,在偏序关系下,它的每一对元素都是不可比的。,对于属于P的两个元素x、y,若有x y 或 y x,则x和y被称作是可比的,否则被称为不可比的。,E中的偏序关系: 对于边u,vE, u v当且仅当u = v或图G中存在 v到 u的一条路径。,问题的偏序集模型,图G可以定义成一个偏序集E:,E中的元素是图G中的边;,u,v,u v,问题的偏序集模型,因此,原问题可以重新用偏序集语言表述为 :,将偏序集(E, )划分成最少的链,使得这些链的并集包含所有E中的元素。,可以发现,图G中从最高点到最低点的
7、路径对应了E的一个链。,目标的转化,直接计算链的最少个数,与网络流没有差别,唯有,继续转化目标,目标的转化,链和反链的计数满足下列关系:,Dilworth定理 令(E, )是一个有限偏序集,并令LA是E中最大反链的大小,SC是将E划分成最少的链的个数。在E中,有 LA = SC。,求E中最长反链的大小,目标最终转化为:,求最长的反链,由偏序集E的定义可以知道:,偏序集E中的反链对应着图G中的一些边,其中任意两条边之间都不能互达。,右图橙色线段便是样例的最长反链,如果用一条线将最长反链所对应的边从左到右连起来,那么这条线不会与平面图中的其它边相交 !,这些线段满足如下性质:,求最长的反链,换句话
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本 思想 方法
链接地址:https://www.31doc.com/p-3290082.html