算法合集之《平面图在信息学中的应用》

《算法合集之《平面图在信息学中的应用》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、平面图在信息学中的应用海南省海南中学刘才良引言平面图是图论中一类重要的图，在实际生产中应用非常广泛。比如集成电路的设计就用到平面图理论。在信息学中，虽然有关平面图的题目并不多见，但对于某些题目，如果通过建模转化，应用平面图的性质，将大大提高算法的效率。因此，掌握一些平面图理论会对我们有很大的帮助。相关定义、定理及推论平面图一个无向图G=，如果能把它画在平面上，且除V中的节点外，任意两条边均不相交，则称该图G为平面图。例如：图(a)经变动后成为(b)，故图(a)为平面图。而图(c)无论如何

2、变动，总出现边相交，图(c)为非平面图。(a)(b)(c)相关定义、定理及推论面设G为一平面图，若由G的一条或多条边所界定的区域内不含图G的节点和边，这样的区域称为G的一个面，记为f。包围这个区域的各条边所构成的圈，称为该面f的边界，其圈的长度，称为该面f的度，记为d(f)。为强调平面图G中含有面这个元素，把平面图表示为G=，其中F是G中所有面的集合。相关定义、定理及推论定理1：若G=是连通平面图，则∑f∈Fd(f)=2

3、E

4、.定理2：若G=是连通平面图，

5、则

6、V

7、-

8、E

9、+

10、F

11、=2.证明：首先假定G是树，则

12、E

13、=

14、V

15、-1，G只有一个无限面，因此

16、V

17、-

18、E

19、+

20、F

21、=

22、V

23、-(

24、V

25、-1)+1=2.现在假设G不是树，由于G是连通的，故G中至少存在一个基本圈C，于是G必有一个有限面f，而f的边界是由基本圈C及可能连同计算两次的一些边组成.如果从G中删去基本圈C上的一条边后得到的平面图G1=，则

26、V1

27、=

28、V

29、，

30、E1

31、=

32、E

33、-1，

34、F1

35、=

36、F

37、-1，故

38、V1

39、-

40、E1

41、+

42、F1

43、=

44、V

45、-

46、E

47、+

48、F

49、，仿此做下去，最

50、终得到G的一棵生成树T0=，于是

51、V

52、-

53、E

54、+

55、F

56、=

57、V0

58、-

59、E0

60、+

61、F0

62、=2.相关定义、定理及推论推论1：给定连通简单平面图G=，若

63、V

64、≥3，则

65、E

66、≤3

67、V

68、-6且

69、F

70、≤2

71、V

72、-4.推论2：设G=是连通简单平面图，若

73、V

74、≥3，则存在v∈V，使得d(v)≤5.邻接表、散列表结构O(

75、V

76、)VS邻接矩阵结构O(

77、V

78、2)推论1：

79、E

80、=O(

81、V

82、)应用-例1:水平可见线段(CEPC2001)平面上有N(N<=8000)条互不相连的竖

83、直线段。如果两条线段可以被一条不经过第三条竖直线段的水平线段连接，则这两条竖直线段被称为“水平可见”的。三条两两“水平可见”的线段构成一个“三元组”。求给定输入中“三元组”的数目。（坐标值为0到8000的整数）应用-例1:水平可见线段(CEPC2001)分析把线段看成点若两条线段水平可见，则在对应两点之间连一条边，建立无向图G统计G中的三角形的数目应用-例1:水平可见线段(CEPC2001)算法一设数组C[I]（I=0..2Ymax），C[2y]表示覆盖y点的最后一条线段，C[2y+1]表示覆盖区

84、间(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(其他情

85、形)线段树的存储：使用完全二叉树的数组结构，可以免去复杂的指针运算和不必要的空间浪费。如何建立图G？时间性能分析排序：O(NlogN)检索：O(NlogYmax)插入：O(NlogYmax)总计：O(NlogYmax)空间性能分析线段：O(N)线段树：O(Ymax)边表：O(N)应用-例1:水平可见线段(CEPC2001)算法一枚举所有的三元组，判断三个顶点是否两两相邻。由于总共有Cn3个三元组，因此时间复杂度为O(N3)算法二枚举一条边，再枚举第三个顶点，判断是否与边上的两个端点相邻。根据水平

86、可见的定义可知G为平面图，G中的边数为O(N)，故算法二的复杂度为O(N2)算法一与算法二的比较算法一只是单纯的枚举，没有注意到问题的实际情况，而实际上三角形的数目是很少的，算法一作了许多无用的枚举，因此效率很低。算法二从边出发，枚举第三个顶点，这正好符合了问题的实际情况，避免了许多不必要的枚举，所以算法二比算法一更加高效。统计图G中三角形的数目应用-例1:水平可见线段(CEPC2001)算法三—换个角度，从点出发每次选取度最小的点v，由推论2知d(v)≤5，只需花常数时间就可