《平面图在信息学中的应用》由会员分享,可在线阅读,更多相关《平面图在信息学中的应用(23页珍藏版)》请在金锄头文库上搜索。
1、平面图在信息学中的应用,海南省海南中学 刘才良,引言,平面图是图论中一类重要的图,在实际生产中应用非常广泛。比如集成电路的设计就用到平面图理论。在信息学中,虽然有关平面图的题目并不多见,但对于某些题目,如果通过建模转化,应用平面图的性质,将大大提高算法的效率。因此,掌握一些平面图理论会对我们有很大的帮助。,相关定义、定理及推论,平面图 一个无向图G=,如果能把它画在平面上,且除V中的节点外,任意两条边均不相交,则称该图G为平面图。,例如:图(a)经变动后成为(b),故图(a)为平面图。而图(c)无论如何变动,总出现边相交,图(c)为非平面图。,相关定义、定理及推论,面 设G为一平面图,若由G的
2、一条或多条边所界定的区域内不含图G的节点和边,这样的区域称为G的一个面,记为f。包围这个区域的各条边所构成的圈,称为该面f的边界,其圈的长度,称为该面f的度,记为d(f)。为强调平面图G中含有面这个元素,把平面图表示为G=,其中F是G中所有面的集合。,相关定义、定理及推论,定理1:若G=是连通平面图,则fFd(f)=2|E|. 定理2:若G=是连通平面图,则|V|-|E|+|F|=2.,证明: 首先假定G是树,则|E|=|V|-1,G只有一个无限面, 因此|V|-|E|+|F|=|V|-(|V|-1)+1=2. 现在假设G不是树,由于G是连通的,故G中至少存在一个基本圈C,于是G必有一个有限面
3、f,而f的边界是由基本圈C及可能连同计算两次的一些边组成.如果从G中删去基本圈C上的一条边后得到的平面图G1=,则|V1|=|V|,|E1|=|E|-1,|F1|=|F|-1,故|V1|-|E1|+|F1|=|V|-|E|+|F|,仿此做下去,最终得到G的一棵生成树T0=,于是|V|-|E|+|F|=|V0|-|E0|+|F0|=2.,相关定义、定理及推论,推论1:给定连通简单平面图G=,若|V|3,则|E|3|V|-6且|F|2|V|-4. 推论2:设G=是连通简单平面图,若|V|3,则存在vV,使得d(v)5.,邻接表、散列表结构O(|V|) VS 邻接矩阵结构O(|V|2),推论1:|E
4、|=O(|V|),应用-例1:水平可见线段(CEPC2001),平面上有N(N=8000)条互不相连的竖直线段。如果两条线段可以被一条不经过第三条竖直线段的水平线段连接,则这两条竖直线段被称为“水平可见”的。三条两两“水平可见”的线段构成一个“三元组”。求给定输入中“三元组”的数目。(坐标值为0到8000的整数),应用-例1:水平可见线段(CEPC2001),分析 把线段看成点 若两条线段水平可见,则在对应两点之间连一条边,建立无向图G 统计G中的三角形的数目,应用-例1:水平可见线段(CEPC2001),算法一 设数组CI(I=02Ymax),C2y表示覆盖y点的最后一条线段,C2y+1表示
5、覆盖区间(y,y+1)的最后一条线段 把线段按从左到右的顺序排序 依次检查每一条线段L(L=y,y) 检查L覆盖的所有整点和单位区间(Cu,u=2y2y) 若Cu0,则G.AddEdge(Cu,L) CuL,O(NlogN) O(N) O(Ymax) 总计:O(NYmax),时间性能分析,如何建立图G?,应用-例1:水平可见线段(CEPC2001),算法二 定义线段树T: 设节点N描述区间a,b的覆盖情况 0 (无线段覆盖a,b) 则N.Cover= L (线段L完全覆盖a,b) -1 (其他情形) 线段树的存储: 使用完全二叉树的数组结构,可以免去复杂的指针运算和不必要的空间浪费。,如何建立
6、图G?,时间性能分析 排序:O(NlogN) 检索:O(NlogYmax) 插入:O(NlogYmax) 总计:O(NlogYmax) 空间性能分析 线段:O(N) 线段树:O(Ymax) 边表:O(N),应用-例1:水平可见线段(CEPC2001),算法一 枚举所有的三元组,判断三个顶点是否两两相邻。由于总共有Cn3个三元组,因此时间复杂度为O(N3) 算法二 枚举一条边,再枚举第三个顶点,判断是否与边上的两个端点相邻。根据水平可见的定义可知G为平面图,G中的边数为O(N),故算法二的复杂度为O(N2) 算法一与算法二的比较 算法一只是单纯的枚举,没有注意到问题的实际情况,而实际上三角形的数
7、目是很少的,算法一作了许多无用的枚举,因此效率很低。 算法二从边出发,枚举第三个顶点,这正好符合了问题的实际情况,避免了许多不必要的枚举,所以算法二比算法一更加高效。,统计图G中三角形的数目,应用-例1:水平可见线段(CEPC2001),算法三换个角度,从点出发 每次选取度最小的点v,由推论2知d(v)5,只需花常数时间就可以计算含点v的三角形的数目. 应用二叉堆可以提高寻找和删除点v的效率,总的时间复杂度仅为O(NlogN) 算法二与算法三的比较 算法二是以边作为出发点的,从整体上看,平面图中三角形的个数只是O(N)级的,而算法二的复杂度却是O(N2),这种浪费是判断条件过于复杂造成的。算法
8、三从点出发,则只需要判断某两点是否相邻即可。,有没有更好的办法?,应用-例2:洞穴(CEOI97),在同一水平面上有N(N=500)个洞穴,洞穴之间有通道相连,且每个洞穴恰好连着三个通道。通道与通道不相交,每个通道都有一个难度值,现从1号洞穴开始遍历所有的洞穴刚好一次并回到洞穴1,求通过通道难度值之和的最小值。(给定所有通道的信息和在外圈上的洞穴),应用-例2:洞穴(CEOI97),分析 本题求的是最优路径,但最优路径具备什么性质并不明显,故考虑深度优先搜索。 N最大达到500,考虑剪枝以提高效率。 基本剪枝条件:若当前路径的难度值的总和比当前最优值大则放弃当前路径。 为了找到强剪枝条件,考虑
9、问题所具有的特性 所有点的度数为3 所给的图是平面图 外圈上的点已知,应用-例2:洞穴(CEOI97),情形一 考虑路径1-3-5-6-12-10,由于每个洞穴必须被访问到,而11号洞穴只有一条可用通道9-11,访问11后不能再回到1,故该路径不可能遍历所有点。 剪枝条件一 在所有未访问的洞穴中,与其相邻的已访问过的洞穴(第1个与当前访问的最后一个除外)的个数小于等于1。,应用-例2:洞穴(CEOI97),情形二 路径1-3-7-9-10-8-4把图分成两部分,而且两部分中都有未访问过的点。由于图是平面图,其中必有一部分点不能被访问到。 剪枝条件二 设外圈上的点按连接顺序为1,a2,ak,则访
10、问的顺序只能为: 1,a2,a3,ak,1.,应用-例3:地图着色(ACM Shanghai 2000),分析: 把每个区域看成点,相邻区域之间连一条边,则问题转化为对每个点着色并使得相邻点颜色不同。 根据地图的平面性可知:转化后的图是平面图。,给定一地图,要求用不超过5种颜色涂每一个区域,使得相邻区域的颜色不同。(区域数=500),对于任意平面图G,是否都能用不超过5种颜色着色?,应用-例3:地图着色(ACM Shanghai 2000),定理:对于任意平面图G,都能用不超过5种颜色着色. 证明:只需考虑G是连通简单平面图的情形. 若|V|5,则命题显然成立. 假设对所有的平面图G=,当|V
11、|k时命题成立.现在考虑图G1=,|V1|=k+1的情形.由推论2可知:存在v0V1,使得d(v0)5.在图G1中删去v0,得图G1-v0.由归纳,图G1-v0可用5种颜色着色. 若邻接结点使用颜色数不超过4,则可对v0着色,得到一个最多是五色的图G1.,应用-例3:地图着色(ACM Shanghai 2000),若d(v0)=5且各邻接点分别着不同的颜色,则设与之相邻的点的按顺时针排列为v1,v2,v3,v4,v5.它们分别着不同的颜色c1,c2,c3,c4,c5. 考虑点集Vc1,c3=v|vV(G1-v0)a(v)=c1或c3所诱导的G1-v0的子图.若v1,v3属于的不同的分图,则在v
12、1所在的分图中,调换颜色c1与c3后,v1,v2,v3,v4,v5五个点是四着色的,再令v0着c1色,得到G1的一种五着色.,应用-例3:地图着色(ACM Shanghai 2000),若v1,v3属于的同一的分图,则点集Vc1,c3v0所诱导的G1的子图中含有一个圈C,而v2,v4不能同时在圈的内部或外部,即v2,v4不是邻接点,于是考虑Vc2,c4=v|vV(G1-v0)a(v)=c2或c4所诱导的子图,v2,v4必属于的不同的分图.做与上面类似的调整,又可得到G1的一种五着色. 故对任何连通简单平面图G,G是五着色的.,应用-例3:地图着色(ACM Shanghai 2000),算法:
13、procedure Paint(G:Graph); 找出度最小的点v0 Paint(G-v0) 考虑图G,若无法对v0着色,则对v0的相邻点,枚举所有点对,直到找到属于不同分图的点对,对其进行调整. 任选剩下的一种颜色,对v0着色 时间复杂度:O(N2) 空间复杂度:O(N),总结,以上例子分别论述了平面图理论在几类信息学问题中的应用。我们研究平面图就是为了更深刻地认识平面图,提高算法效率,但有时候单独应用平面图理论还不够,还需要和其它理论知识综合起来应用。然而要达到理想的效果并非一朝一夕的事情,它还需要我们平时多积累、多思考,遇到问题时才能运用自如。相信随着对平面图的研究不断深入,平面图的应用一定会更加广阔。,谢谢!,