树图与最小生成树

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,6.2 树,图与最小生成树,一般研究无向图,树图：倒置的树，,根,(,root,)在上，,树叶,(,leaf,)在下,多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图,1,6.2.1,树的定义及其性质,任两点之间有且只有一条路径的图称为树(tree)，记为T,树的性质：,最少边的连通子图，树中必不存在回路,任何树必存在次数为 1 的点,具有 n 个节点的树 T 的边恰好为 n1 条，反之，任何有n 个节点，n1 条边的连通图必是一棵树,6.2.2 图的生成树,树 T 是连通图 G 的生成树(spanning tree)，假设 T 是 G的子图且包含图 G 的所有的节点；包含图 G 中局部指定节点的树称为 steiner tree,每个节点有唯一标号的图称为标记图，标记图的生成树称为标记树(labeled tree),Caylay 定理：n(2)个节点，有nn2个不同的标记树,2,图的生成树,如何找到一棵生成树,深探法(depth first search)：任选一点标记为 0 点开始搜索，选一条未标记的边走到下一点，该点标记为 1，将走过的边标记；假设已标记到 i 点，总是从最新标记的点向下搜索，假设从 i 点无法向下标记，即与 i 点相关联的边都已标记或相邻节点都已标记，那么退回到 i 1 点继续搜索，直到所有点都被标记,广探法(breadth first search)：是一种有层级结构的搜索，一般得到的是树形图,3,最小生成树,有n 个乡村，各村间道路的长度是的，如何敷设光缆线路使 n 个乡村连通且总长度最短,显然，这要求在边长度的网路图中找最小生成树,最小生成树的算法：,Kruskal 算法：将图中所有边按权值从小到大排列，依次选所剩最小的边参加边集 T，只要不和前面参加的边构成回路，直到 T 中有 n1 条边，那么 T 是最小生成树,Kruskal 算法基于下述定理,定理 3 指定图中任一点vi，如果 vj 是距 vi 最近的相邻节点，那么关联边 eij 必在某个最小生成树中。,推论 将网路中的节点划分为两个不相交的集合V1和V2，V2=VV1，那么V1和V2间权值最小的边必定在某个最小生成树中。,4,最小生成树,最小生成树不一定唯一,定理 3 推论是一个构造性定理，它指示了找最小生成树的有效算法,Prim 算法：不需要对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上操作，后者适合计算机运算,边权矩阵上的 Prim 算法：,1、根据网路写出边权矩阵，两点间假设没有边，那么用表示；,2、从 v1 开始标记，在第一行打 ，划去第一列；,3、从所有打 的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打 ；,4、假设所有列都划掉，那么已找到最小生成树(所有画圈元素所对应的边)；否那么，返回第 3 步。,该算法中，打 行对应的节点在 V1中，未划去的列在 V2中,5,最小生成树,Prim,算法是多项式算法,Prim算法可以求最大生成树,网路的边权可以有多种解释，如效率,次数受限的最小生成树尚无有效算法,最小 Steiner 树尚无有效算法,6,