图论第二节.pptVIP

图与网络分析 第二节 最小树问题 第五章 图与网络分析 1.图的基本概念 2.最小树问题 3.最短路问题 4.最大流问题 5.最小费用最大流问题 * 本 章 内 容 第二节 最小树问题 一、树及其性质 定义1： 无圈的连通图称为树。树一般用T表示。 定理1： 任给树T=（V，E），若P（T）≥2，则 T中至少有两个悬挂点。 证明：设 μ=（v1，v2，…，vk）是G中含边数最多的一条初等链，因 p（T ）≥2，并且T是连通的，故链 μ 中至少有一条边，从而v1与vk是不同的 。 现证v1是悬挂点，即d（v1）=1。 反证法：如d（v1）≥2，则存在边[v1，vm]，使m≠2， 若vm不在μ上， v1 v2 vk vm 那么（vm，v1，v2，…，vk）比μ链边数多一条，与μ是边数最多的链矛盾。 若vm在μ上 v1 v2 vk vm （v1，v2，…， vm， v1）是圈，与T是树矛盾。 所以必有d（v1）=1，即v1是悬挂点。 同理可证：vk也是悬挂点。所以T至少有两个悬挂点。 （1）T是一个树。 （2）T无圈，且m=n-1。 （3）T连通，且m=n-1。 定理2 图T=（V，E）， p=n， q=m，则下列关于 树的说法是等价的。 边数=点数-1 （4）T无圈，但每加一条新边即得唯一一个圈。 （5）T连通，但每丢掉一条边就不连通。 （6）T中任意两点，有唯一链相连。 证明：（1）→（2） 由于T是树，由定义知T连通且无圈。只须证明m=n-1。 归纳法：当n=2时，由于T是树，所以两点间显然有且 仅有一条边，满足m=n-1。 假设 n=k-1时命题成立，即有k-1个顶点时，T有k-2条边。 当n=k时，因为T连通无圈，k个顶点中至少有一个点次为1。设此点为u，即u为悬挂点，设连接点u的悬挂边为[v，u]，从T中去掉[v，u]边及点u ，不会影响T的连通性，得图T’，T’为有k-1个顶点的树，所以T’有k-2条边，再把（ v，u）、点u加上去，可知当T有k个顶点时有k-1条边。 （2）→（3） 只须证T是连通图。 反证法 设T不连通，可以分为l个连通分图（l≥2）， 设第i个分图有ni个顶点， 因为第i个分图是树，所以有ni-1条边，l个分图共有边数为： 与已知矛盾。所以T为连通图。 （3）→（4）、（4）→（5）、（5）→（6）、及（6）→（1）的证明略。 二、图的支撑树 定义2 设图T=[V，E’]是图G=（V，E）的支撑子图，如果T是一个树，则称T是G的一个支撑树。 v1 v3 v2 v4 v5 v6 （a） v3 v1 v2 v4 v5 v6 （b） （b）是（a）的一个支撑树。 定理3 图G有支撑树的充分必要条件是图G是连通的。 证明：必要性是显然的。 充分性： 设G是连通的，如果G不含圈，则G本身是 一个树，从而是它自身的一个支撑树。 现设G含图，从圈中任意去掉一条边，得G的一个支撑子图G1，如G1不含圈，则G1是G的一个支撑树；如G1含圈，则从G1中任取一圈，从圈中再任意去掉一条边，得G的一个支撑子图G2，如此重复，终可得G的一个不含圈的支撑子图Gk，于是Gk是G的一个支撑树。 （一）破圈法 （二）避圈法 在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与{e1，e2}不构成圈的边e3。一般设已有{e1，e2，…，ek}，找一条与{e1，e2，…，ek}中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。 v1 v2 v3 v4 v5 v6 v1 v3 v1 v3 v2 v1 v3 v2 v5 v6 v1 v3 v2 v5 v6 v4 v1 v3 v2 v5 三、最小支撑树问题 定义3 设有连通图G=（V，E），G的任一边ek=[vi，vj] 有一个非负权w（ek）=wij（wij≥0）,T=（V，E’） 是G的一个支撑树，称 为树T的权。 如果支撑树T*的权w（T*）是G的所有支撑树的权中最小的，则称T*是G的最小支撑树（简称最小树）。即 最小树问题，即求网络G的最小支撑树。 （一）避圈法（Kruskal） 思想：在图中取一条最小权的边，以后每一步中，总 从未被选取的边中选一条权最小的边，并使