算法合集之〔平面图在信息学中的应用〕.ppt

平面图在信息学中的应用 海南省海南中学 刘才良 引言 平面图是图论中一类重要的图，在实际生产中应用非常广泛。比如集成电路的设计就用到平面图理论。在信息学中，虽然有关平面图的题目并不多见，但对于某些题目，如果通过建模转化，应用平面图的性质，将大大提高算法的效率。因此，掌握一些平面图理论会对我们有很大的帮助。 相关定义、定理及推论 平面图 一个无向图G=V，E，如果能把它画在平面上，且除V中的节点外，任意两条边均不相交，则称该图G为平面图。 相关定义、定理及推论 面 设G为一平面图，若由G的一条或多条边所界定的区域内不含图G的节点和边，这样的区域称为G的一个面，记为f。包围这个区域的各条边所构成的圈，称为该面f的边界，其圈的长度，称为该面f的度，记为d(f)。为强调平面图G中含有面这个元素，把平面图表示为G=V，E，F，其中F是G中所有面的集合。 相关定义、定理及推论 定理1：若G=V，E，F是连通平面图，则∑f∈Fd(f)=2|E|. 定理2：若G=V，E，F是连通平面图，则|V|-|E|+|F|=2. 相关定义、定理及推论 推论1：给定连通简单平面图G=V，E，F，若|V|≥3，则|E|≤3|V|-6且|F|≤2|V|-4. 推论2：设G=V，E，F是连通简单平面图，若|V|≥3，则存在v∈V，使得d(v)≤5. 应用-例1:水平可见线段(CEPC2001) 　　　平面上有N(N=8000)条互不相连的竖直线段。如果两条线段可以被一条不经过第三条竖直线段的水平线段连接，则这两条竖直线段被称为“水平可见”的。三条两两“水平可见”的线段构成一个“三元组”。求给定输入中“三元组”的数目。（坐标值为0到8000的整数） 应用-例1:水平可见线段(CEPC2001) 分析 把线段看成点 若两条线段水平可见，则在对应两点之间连一条边，建立无向图G 统计G中的三角形的数目 应用-例1:水平可见线段(CEPC2001) 算法一 设数组C[I]（I=0..2Ymax），C[2y]表示覆盖y点的最后一条线段，C[2y+1]表示覆盖区间(y,y+1)的最后一条线段 把线段按从左到右的顺序排序 依次检查每一条线段L(L=[y，y]) 检查L覆盖的所有整点和单位区间（C[u]，u=2y..2y） 若C[u]≠0，则G.AddEdge(C[u]，L) C[u]←L 应用-例1:水平可见线段(CEPC2001) 算法二 定义线段树T： 设节点N描述区间[a,b]的覆盖情况 0 (无线段覆盖[a,b]) 则N.Cover= L (线段L完全覆盖[a,b]) -1 (其他情形) 线段树的存储：使用完全二叉树的数组结构，可以免去复杂的指针运算和不必要的空间浪费。 应用-例1:水平可见线段(CEPC2001) 算法一枚举所有的三元组，判断三个顶点是否两两相邻。由于总共有Cn3个三元组，因此时间复杂度为O(N3) 算法二枚举一条边，再枚举第三个顶点，判断是否与边上的两个端点相邻。根据水平可见的定义可知G为平面图，G中的边数为O(N)，故算法二的复杂度为O(N2) 算法一与算法二的比较算法一只是单纯的枚举，没有注意到问题的实际情况，而实际上三角形的数目是很少的，算法一作了许多无用的枚举，因此效率很低。算法二从边出发，枚举第三个顶点，这正好符合了问题的实际情况，避免了许多不必要的枚举，所以算法二比算法一更加高效。 应用-例1:水平可见线段(CEPC2001) 算法三—换个角度，从点出发每次选取度最小的点v，由推论2知d(v)≤5，只需花常数时间就可以计算含点v的三角形的数目.应用二叉堆可以提高寻找和删除点v的效率，总的时间复杂度仅为O(NlogN) 算法二与算法三的比较算法二是以边作为出发点的，从整体上看，平面图中三角形的个数只是O(N)级的，而算法二的复杂度却是O(N2)，这种浪费是判断条件过于复杂造成的。算法三从点出发，则只需要判断某两点是否相邻即可。 应用-例2:洞穴(CEOI97) 　　　在同一水平面上有N(N=500)个洞穴，洞穴之间有通道相连，且每个洞穴恰好连着三个通道。通道与通道不相交，每个通道都有一个难度值，现从1号洞穴开始遍历所有的洞穴刚好一次并回到洞穴1，求通过通道难度值之和的最小值。(给定所有通道的信息和在外圈上的洞穴) 应用-例2:洞穴(CEOI97) 分析 本题求的是最优路径，但最优路径具备什么性质并不明显，故考虑深度优先搜索。 N最大达到500，考虑剪枝以提高效率。 基本剪枝条件：若当前路径的难度值的总和比当前最优值大则放弃当前路径。 为了找到强剪枝条件，考虑问题所具有的特性 所有点的度数为3 所给的图是平面图 外圈上的点已知 应用-例2:洞穴(CEOI97) 情形一考虑路径1-3-5-6-12-10，由于每个洞穴