图论与网络优化ch3.pdf

3 树/3.1 树的基本性质 Graph Theory/ 图论 树：无圈的连通图。森林：无圈图. 举例： (1) 碳氢化合物的分子式都是树形结构。 (2)决策树：用逻辑关系做出判决的树称为 决策树。 (3)数据树：表示数据的树被程序员称为数 据树。 Graph Theory/ 图论 树的特性 定理3.1.1：一个简单图T是树当且仅当T 中任意 两个顶点之间有且仅有一条路连接。 定理3.1.2：下述论断等价： (1)图T是树；(2)T连通且q (T)=p(T)-1; (3)T无圈且q (T)=p(T)-1;(4)T连通且T的每条边都 是割边；(5)T无圈且对任意两个不相邻的顶点u 和v，T+uv有且只有一个圈. 定理3.1.4：树T的每一个非悬挂点都是T的割点. 很容易得到第二章第二节引理2和定理3。 Graph Theory/ 图论 3.2 生成树/spanning tree 定义1：如果树T是连通图G的生成子图，那末 称T是G的一棵生成树 （支撑树）。 定义1‘: 如果G是一个包含k个成分的分离图,则 相应的k个生成树所组成的图称为生成森林。 定理3.2.1 G是连通图当且仅当G含有生成树. 必要性：逐步移去图中圈上的边，直到没有圈 为止，这样就能得到G的一棵支撑树。(破圈法) 避圈法：在v(G) 中逐次添加E(G)中的边，要求 每次添加之后所得子图不含圈，一直进行到无 法再添边为止。 Graph Theory/ 图论 定义3：设T是连通图G的一棵生成树,称 T G T 为T的余树.T 中的边称为树枝, T中的边称为G 关于T的弦. • (树枝和弦都是相对于某一棵生成树而言，不 同的生成树对应不同的树枝和弦) 说明: 对连通图G的任意生成树T,总有p-1条树 枝和q-p+1条弦。 举例说明。 Graph Theory/ 图论 怎样找出所有的生成树(补充一种方法) 初等变换：在一棵生成树上加一条弦,删除 一条树枝而生成一棵新的生成树的变换 称为初等树变换。 树之间的距离：G中两棵支撑树T1和T2 间的距离是它们之间不相同边数的一半。 定理: 从图G的任何支撑树出发，通过一系 列初等树变换,总能找到G的所有支撑树. 3.3 最小生成树 1.最小生成树性质 用贪心算法设计策略可以设计出构造最小生成树 的有效算法。本节介绍的构造最小生成树的Prim算法 和Kruskal算法都可以看作是应用贪心算法设计策略的 例子。尽管这2个算法做贪心选择的方式不同，它们都 利用了下面的最小生成树性质： 设G=(V,E)是连通带权图，U是V 的真子集。如果 (u,v)E，且u U ，v V-U ，且在所有这样的边中， (u,v)的权c[u][v]最小，那么一定存在G 的一棵最小生 成树，它以(u,v)为其中一条边。这个性质有时也称为 MST性质。 6 2012年5月 3.3 最小生成树 2.Prim算法 设G=(V,E)是连通带权图，V={1,2, …,n}。 构造G 的最小生成树的Prim算法的基本思想是：首 先置S={1}，然后，只要S是V 的真子集，就作如下