如果一个图中任意两个顶点vi,vj之间存在vi到达vj的路径,或vj到达vi的路径,则称该图是单向连通的。试证明单向连通的有向无环图具有唯一的拓扑有序序列。
Voronoi图。Voronoi图最早应用在气象学中,荷兰气候学家ThiessenA.H.利用它研究降雨量的问题。
所给出的对平面的剖分.称为以P.为生成元的Voronoi图,简称V图。图中的顶点和边分别称为Voronoi点和Voronoi边,V(p)称为点Pi的Voronoi区域(多边形),其中d(p,p)为点p和点P:之间的欧几里得距离。Voronoi图将相邻两个生成元相连接,并且做出连接线段的垂直评分线,这些垂直平分线之间的交线就形成一些多边形,这样就把整个平面剖分成一些分区域,一个分区域只含有一个生成元,分区域内生成元的属性可以代替此分区域的属性,而且可以根据分区域的面积作为权重推测出该区城中生成元的平均水平。若两个生成元Pi,Pj的Voronoi区城有公共边,就连接这两个点,以此类推遍历这n个生成元,可以得到一个连接点集S的唯一确定的网络,称为Delaunay三角网格,图4.13是Matlab软件画出的10平面点的Voronoi图及对偶Delaunay三角网格图。
Voronoi图具有下列重要性质:
(1)Voronoi图与Delaunay三角网格图对偶;
(2)Voronoi图具有局域动态性,即增加和删除--个生成元只影响相邻生成元的Voronoi区域;
(3)如果点P.在区域V(p.)中,则p到各生成元的距离中,到生成元P的距离最小;
(4)两个相邻Voronoi区域的公共边上任意--点到这两个区域的生成元距离相等;
(5)Voronoi区域的顶点到邻近的生成元的距离相等,即与这个顶点有关的Voronoi区域的生成元共圆.称这个圆为最大空圆。
画出表4.18中数据对应的10个点的Voronoi图及其对偶Delauny三角网格图。
A.反转图中所有边的方向
B.按照设定条件取出子图
C.取两个图的公共顶点和边作为新图,并保持前一个图顶点与边的属性
D.合并边相同的属性
A.树可以看作图的特例
B.树中有一个特殊的元素(根),而图中每个元素的“地位”是一样的
C.图和树中的边沿任意轴旋转后,各元素间的逻辑关系保持不变
D.树中任意两个元素间有唯一的简单路径,而图中任意两个元素间可能有零或多条简单路径
同时有两个函数:max(i,j)和min(i,j),分别计算下标i和j中的大者与小者。试利用它们给出求任意一个A[i][j]在B中存放位置的公式。
问题描述:给定有向图G=(V,E).设P是G的一个简单路(顶点不相交)的集合.如果V中每个顶点恰好在P的条路上,则称P是G的一个路径覆盖.P中路径可以从V的任何一个项点开始,长度也是任意的,特别地,可以为0.G的最小路径覆盖是G的所含路径条数最少的路径覆盖.
设计一个有效算法求一个有向无环图G的最小路径覆盖.
[设V={1,2,...,n},如下构造网络G1=(V1,E1):
每条边的容量均为1.求网络G1的(x0,y0)最大流.]
算法设计:对于给定的有向无环图G,找出G的一个最小路径覆盖.
数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和m.n是给定有向无环图G的顶点数,m是G的边数.接下来的m行,每行有2个正整数i和j,表示一条有向边(i,j).
结果输出:将最小路径覆盖输出到文件output.txt.从第1行开始,每行输出一条路径.文件的最后一行是最少路径数.