平面图在信息学中的应用.ppt

应用-例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]←LO(NlogN)O(N)O(Ymax)总计：O(NYmax)时间性能分析如何建立图G？应用-例1:水平可见线段(CEPC2001)算法二定义线段树T：设节点N描述区间[a,b]的覆盖情况 0 (无线段覆盖[a,b])则N.Cover= L (线段L完全覆盖[a,b]) -1 (其他情形)线段树的存储：

使用完全二叉树的数组结构，可以免去复杂的指针运算和不必要的空间浪费。如何建立图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)算法一与算法二的比较

算法一只是单纯的枚举，没有注意到问题的实际情况，而实际上三角形的数目是很少的，算法一作了许多无用的枚举，因此效率很低。

算法二从边出发，枚举第三个顶点，这正好符合了问题的实际情况，避免了许多不必要的枚举，所以算法二比算法一更加高效。统计图G中三角形的数目应用-例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，由于每个洞穴必须被访问到，而11号洞穴只有一条可用通道9-11，访问11后不能再回到1，故该路径不可能遍历所有点。剪枝条件一

在所有未访问的洞穴中，与其相邻的已访问过的洞穴（第1个与当前访问的最后一个除外）的个数小于等于1。410912117856213应用-例2:洞穴(CEOI97)情形二

路径1-3-7-9-10-8-4把图分成两部分，而且两部分中都有未访问过的点。由于图是平面图，其中必有一部分点不能被访问到。剪枝条件二

设外圈上的点按连接顺序为1,a2,…,ak，则访问的顺序只能为：

1,…,a2,…,a3,…,…,…,ak,…,1.109121178564213应用-例3:地图着色(ACMShanghai2000)分析：把每个区域看成点，相邻区域之间连一条边，则问题转化为对每个点着色并使得相邻点颜色不同。根据地图的平面性可知：转化后的图是平面图。给定一地图，要求用不超过5种颜色涂每一个区域，使得相邻区域的颜色不同。（区域数=500）对于任意平面图G，是否都能用不超过5种颜色着色？***********************平