我的运筹课件图论

1、 第二节 最小树问题一、树及其性质定义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，使m2， 若vm不在上，v1v2vkvm 那么（vm，v1，v2，vk）比链边数多一条，与是边数最多的链矛盾。若vm在上v1v2vkvm（v1，v2， vm， v1）是圈，与T是树矛盾。 所以必有d（v1）=1，即v1是悬挂

2、点。同理可证：vk也是悬挂点。所以T至少有两个悬挂点。定理2 图T=（V，E）， p=n， q=m，则下列关于 树的说法是等价的。（1）T是一个树。（2）T无圈，且m=n-1。（3）T连通，且m=n-1。边数=点数-1（1）T是一个树。（2）T无圈，且m=n-1。（3）T连通，且m=n-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个

3、顶点时，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个连通分图（l2）， 设第i个分图有ni个顶点， 因为第i个分图是树，所以有ni-1条边，l个分图共有边数为：与已知矛盾。所以T为连通图（3）（4）、（4）（5）、（5）（6）、及（6）（1）的证明略。二、图的支撑树 定义2 设图T=V，

4、E是图G=（V，E）的支撑子图，如果T是一个树，则称T是G的一个支撑树。v3v1v2v4v5v6（a）v3v1v2v4v5v6（b）（b）是（a）的一个支撑树。定理3 图G有支撑树的充分必要条件是图G是连通的。证明：必要性是显然的。充分性： 设G是连通的，如果G不含圈，则G本身是 一个树，从而是它自身的一个支撑树。 现设G含圈，从圈中任意去掉一条边，得G的一个支撑子图G1，如G1不含圈，则G1是G的一个支撑树；如G1含圈，则从G1中任取一圈，从圈中再任意去掉一条边，得G的一个支撑子图G2，如此重复，终可得G的一个不含圈的支撑子图Gk，于是Gk是G的一个支撑树。（一）破圈法（二）避圈法 在图中任

5、取一条边e1，找一条与e1不构成圈的边e2，再找一条与e1，e2不构成圈的边e3。一般设已有e1，e2，ek，找一条与e1，e2，ek中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。v3v1v2v4v5v6v3v1v2v3v1v2v5v3v1v2v5v4v3v1v2v5v4v6三、最小支撑树问题定义3 设有连通图G=（V，E），G的任一边ek=vi，vj 有一个非负权w（ek）=wij（wij0）,T=（V，E） 是G的一个支撑树，称为树T的权。 如果支撑树T*的权w（T*）是G的所有支撑树的权中最小的，则称T*是G的最小支撑树（简称最小树）。即最小支撑树问题，即求网络G的最

6、小树。（一）避圈法（Kruskal）思想：在图中取一条最小权的边，以后每一步中，总 从未被选取的边中选一条权最小的边，并使 之与已选取的边不构成圈（每一步中，如果有 两条或两条以上的边都是最小权的边，则从中 任选一条）。Kruskal算法步骤：第1步：把G=（V，E）的边按权由小到大排好，即要求w（e1） w （e2） w （em）图G，p=n ，q=m，令i=1 ，j=0 ， E0= ， 检查过的 边数 取的边数最小树的边集Kruskal算法步骤：第1步：把G=（V，E）的边按权由小到大排好，即要求w（e1） w （e2） w （em）图G，p=n ，q=m，令i=1 ，j=0 ， E0=

7、， 第2步：如果（V，Ei-1ei）含圈，Ei=Ei-1，转第3步， 否则转第4步；不要这条边Kruskal算法步骤：第1步：把G=（V，E）的边按权由小到大排好，即要求w（e1） w （e2） w （em）图G，p=n ，q=m，令i=1 ，j=0 ， E0= ， 第2步：如果（V，Ei-1ei）含圈，Ei=Ei-1，转第3步， 否则转第4步；第3步：i换成i+1，如果im，转第2步，否则结束， G没有最小树；第4步：令Ei=Ei-1ei，j换成j+1，如果j=n-1，结束， （V，Ei）是所求最小树，否则转第3步。 取定这条边第4步：令Ei=Ei-1ei，j换成j+1，如果j=n-1，结束

8、， （V，Ei）是所求最小树，否则转第3步。 例： 某工厂内联结六个车间的道路如图示。已知每 条道路的长，要求沿道路架设联结六个车间的 电话线网，使电话线的总长最小。 2345674v3v1v2v4v5v615解：将各边按权从小到大排为：w23 w24 w45 w 56 w 46 w12 w35 w13 w25i=1 ，j=0 ，E0= ，n=6 ，m=9（V， E0 e23）无圈，E1=E0 e23=e23，j=1 n-1,i=2,（V， E1 e24）无圈，E2=E1 e24=e23, e24，j=2 n-1,i=3,（V， E2 e45）无圈，E3=E2 e45=e23, e24 , e

9、45， j=3 n-1,i=4,（V， E3 e56）无圈，E4=E3 e56=e23, e24 , e45 , e56， j=4 n-1,i=5,（V， E4 e46）含圈，E5=E4,i=6,（V， E5 e12）无圈，E6=E5 e12=e23, e24 , e45 , e56 , e12， j=5 =n-1,结束，（V，E6）是所求的最小树。v32345674v1v2v4v5v615电话线总长最小方案如图，总长15单位。Dijkstra算法 （避圈法）思想：在n-1个独立割集中（这n-1个独立割集由网络 中不同的点集所确定），取每个割集的一条最 小权边，构成一个支撑树，它是一棵最小树。

10、Dijkstra算法步骤：第2步：在Xi所确定的割集（Xi）中选一条最小权 边ek，ek=v，vk， vxi ，第3步：若Xi+1=V，结束，（V，Ei+1）是所求的最 小树。否则，把i换成i+1，返回第2步。第1步： 例：2345674v3v1v2v4v5v615（V，E5）是所求最小树。2345674v3v1v2v4v5v6152345674v3v1v2v4v5v615v62345674v3v1v2v4v515v62345674v3v1v2v4v515v62345674v3v1v2v4v515v62345674v3v1v2v4v515v62345674v3v1v2v4v515（二）破圈法 任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步