树图与最小生成树ppt课件

1、6.2 树图与最小生成树树图与最小生成树 普通研讨无向图 树图：倒置的树，根(root)在上，树叶(leaf)在下 多级辐射制的电信网络、管理的目的体系、家谱、分类学、组织构造等都是典型的树图C1C2C3C4根根叶叶 6.2.1 树的定义及其性质树的定义及其性质 任两点之间有且只需一条途径的图称为树任两点之间有且只需一条途径的图称为树(tree)，记为，记为T 树的性质：树的性质： 最少边的连通子图，树中必不存在回路最少边的连通子图，树中必不存在回路 任何树必存在次数为任何树必存在次数为 1 的点的点 具有具有 n 个节点的树个节点的树 T 的边恰好为的边恰好为 n1 条，反之，任何条，反之，

2、任何有有n 个节点，个节点， n1 条边的连通图必是一棵树条边的连通图必是一棵树 6.2.2 图的生成树图的生成树 树树 T 是连通图是连通图 G 的生成树的生成树(spanning tree)，假设，假设 T 是是 G的子图且包含图的子图且包含图 G 的一切的节点；包含图的一切的节点；包含图 G 中部分指定中部分指定节点的树称为节点的树称为 steiner tree 每个节点有独一标号的图称为标志图，标志图的生成树每个节点有独一标号的图称为标志图，标志图的生成树称为标志树称为标志树(labeled tree) Caylay 定理：定理：n (2)个节点，有个节点，有nn2个不同的标志树个不同

3、的标志树 6.2.2 图的生成树图的生成树 如何找到一棵生成树 深探法(depth first search)：任选一点标志为 0 点开场搜索，选一条未标志的边走到下一点，该点标志为 1，将走过的边标志；假设已标志到 i 点，总是从最新标志的点向下搜索，假设从 i 点无法向下标志，即与 i 点相关联的边都已标志或相邻节点都已标志，那么退回到 i 1 点继续搜索，直到一切点都被标志 广探法(breadth first search)：是一种有层级构造的搜索，普通得到的是树形图ACDBACDBACDBADCB 6.2.3 最小生成树最小生成树 有n 个乡村，各村间道路的长度是知的，如何敷设光缆线路

4、使 n 个乡村连通且总长度最短 显然，这要求在知边长度的网路图中找最小生成树 最小生成树的算法： Kruskal 算法：将图中一切边按权值从小到大陈列，依次选所剩最小的边参与边集 T，只需不和前面参与的边构成回路，直到 T 中有 n1 条边，那么 T 是最小生成树 Kruskal 算法基于下述定理 定理 3 指定图中任一点vi，假设 vj 是距 vi 最近的相邻节点，那么关联边 eij 必在某个最小生成树中。 推论 将网路中的节点划分为两个不相交的集合V1和V2，V2=VV1，那么V1和V2间权值最小的边必定在某个最小生成树中。 6.2.3 最小生成树最小生成树 最小生成树不一定独一 定理 3

5、 推论是一个构造性定理，它指示了找最小生成树的有效算法 Prim 算法：不需求对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上操作，后者适宜计算机运算 边权矩阵上的 Prim 算法： 1、根据网路写出边权矩阵，两点间假设没有边，那么用表示； 2、从 v1 开场标志，在第一行打 ，划去第一列； 3、从一切打 的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打 ； 4、假设一切列都划掉，那么已找到最小生成树(一切画圈元素所对应的边)；否那么，前往第 3 步。 该算法中，打 行对应的节点在 V1中，未划去的列在 V2中 6.2.3 最小生成树最小生成树 97125 .19179810787111275 . 9165 .195 . 9101710111610 Prim算法是多项式算法 Prim算法可以求最大生成树 网路的边权可以有多种解释，如效率 次数受限的最小