《5第五章-最小树问题优秀PPT.ppt》由会员分享，可在线阅读，更多相关《5第五章-最小树问题优秀PPT.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章第五章 最小树问题最小树问题 这一章讲的最小树问题，是图论中有一个很这一章讲的最小树问题，是图论中有一个很重要的极值问题，它的重要性不亚于最短路问题重要的极值问题，它的重要性不亚于最短路问题.5.1 什么是最小树问题什么是最小树问题 定义定义5.1.1 5.1.1 设设G=(V,E)G=(V,E)是一个无向图，假如是一个无向图，假如它具有下述两特性质：它具有下述两特性质：(1)(1)连通；连通；(2)(2)没有圈没有圈就称就称G G是一个树（或一棵树）是一个树（或一棵树）.图图图图5.1.1(a)5.1.1(a)5.1.1(a)5.1.1(a)、(b)(b)(b)(b)中画的都是树的例子
2、中画的都是树的例子中画的都是树的例子中画的都是树的例子.(a)G(a)G1 1(b)G(b)G2 2图图图图 注：树中度为注：树中度为注：树中度为注：树中度为1 1 1 1的顶点称为树叶，度大于的顶点称为树叶，度大于的顶点称为树叶，度大于的顶点称为树叶，度大于1 1 1 1的顶点的顶点的顶点的顶点称为枝点或分支点称为枝点或分支点称为枝点或分支点称为枝点或分支点.前面已经讲过，所谓图G=(V,E)的支撑子图，指的是G的一个子图G1=(V1,E1)，其中V1=V，即G1是由G的全部顶点及一部分边组成的.对于我们来说，特殊重要的是图G(G本身不确定是树)的那些形成树的支撑子图.定义定义定义定义5.1
3、.2 5.1.2 5.1.2 5.1.2 设设设设G=(V,E)G=(V,E)G=(V,E)G=(V,E)是一个无向图，假如是一个无向图，假如是一个无向图，假如是一个无向图，假如T=(V,E1)T=(V,E1)T=(V,E1)T=(V,E1)是是是是G G G G的支撑子图并且的支撑子图并且的支撑子图并且的支撑子图并且T T T T是树，则称是树，则称是树，则称是树，则称T T T T是是是是G G G G的一个的一个的一个的一个支撑树支撑树支撑树支撑树.图图图图 是不是每个图是不是每个图是不是每个图是不是每个图G G G G都有支撑树呢？不见得都有支撑树呢？不见得都有支撑树呢？不见得都有支撑
4、树呢？不见得.很明显，很明显，很明显，很明显，假如假如假如假如G G G G不连通，不连通，不连通，不连通，G G G G就确定不会有支撑树就确定不会有支撑树就确定不会有支撑树就确定不会有支撑树.反过来，我们反过来，我们反过来，我们反过来，我们有有有有:定理定理定理定理5.1.1 5.1.1 5.1.1 5.1.1 连通图确定有支撑树连通图确定有支撑树连通图确定有支撑树连通图确定有支撑树.证明：设证明：设证明：设证明：设G G G G是一个连通图，假如是一个连通图，假如是一个连通图，假如是一个连通图，假如G G G G没有圈，那么没有圈，那么没有圈，那么没有圈，那么G G G G本身就是一个支
5、撑树，假如本身就是一个支撑树，假如本身就是一个支撑树，假如本身就是一个支撑树，假如G G G G有圈，那么任取有圈，那么任取有圈，那么任取有圈，那么任取G G G G的一个的一个的一个的一个圈，并且从这个圈中随意去掉一条边，得到圈，并且从这个圈中随意去掉一条边，得到圈，并且从这个圈中随意去掉一条边，得到圈，并且从这个圈中随意去掉一条边，得到G G G G的一个的一个的一个的一个支撑子图支撑子图支撑子图支撑子图G1,G1,G1,G1,易见易见易见易见G1G1G1G1仍是连通的，假如仍是连通的，假如仍是连通的，假如仍是连通的，假如G1G1G1G1还有圈，就还有圈，就还有圈，就还有圈，就再从某一个圈
6、中去掉一条边，得到再从某一个圈中去掉一条边，得到再从某一个圈中去掉一条边，得到再从某一个圈中去掉一条边，得到G2G2G2G2，G2G2G2G2仍是连通的，仍是连通的，仍是连通的，仍是连通的，这样做下去，直至得到一个不含圈的连通支撑子，这样做下去，直至得到一个不含圈的连通支撑子，这样做下去，直至得到一个不含圈的连通支撑子，这样做下去，直至得到一个不含圈的连通支撑子图图图图GsGsGsGs为止，为止，为止，为止，GsGsGsGs就是就是就是就是G G G G的一个支撑树了的一个支撑树了的一个支撑树了的一个支撑树了.按定理的证明方法得到一个支撑树的过程成为按定理的证明方法得到一个支撑树的过程成为按定
7、理的证明方法得到一个支撑树的过程成为按定理的证明方法得到一个支撑树的过程成为“破圈法破圈法破圈法破圈法”。从破圈的过程可以看出，一个连通图G一般有很多支撑树.因为取定一个圈后，可以从这个圈上随意去掉一条边.去掉的边不一样，得到的支撑树就不同.现在考虑一个连通图G=(V,E)，它的每一条边ej有一个长度l(ej)0.这时，对于G的随意一个支撑树T，我们把属于T的各条边的长度加起来的和叫做树T的长度，记作l(T).如下图：l(T1)=22,l(T2)=17.v v1 1v v2 2v v3 3v v4 4v v5 55 58 86 62 23 36 65 5v v1 1v v2 2v v3 3v
8、v4 4v v5 55 58 86 62 23 36 65 5v v1 1v v2 2v v3 3v v4 4v v5 55 58 86 62 23 36 65 5a:Ga:Gb:Tb:T1 1c:Tc:T2 2图图图图 现在的问题是如何从现在的问题是如何从现在的问题是如何从现在的问题是如何从G G G G的全部支撑树中，把长度最的全部支撑树中，把长度最的全部支撑树中，把长度最的全部支撑树中，把长度最小的支撑树找出来？小的支撑树找出来？小的支撑树找出来？小的支撑树找出来？.通常，我们把长度最小的支撑树叫做最小树通常，我们把长度最小的支撑树叫做最小树通常，我们把长度最小的支撑树叫做最小树通常，我
9、们把长度最小的支撑树叫做最小树.所所所所以上面的问题事实上就是如何把一个图以上面的问题事实上就是如何把一个图以上面的问题事实上就是如何把一个图以上面的问题事实上就是如何把一个图G G G G的最小树找的最小树找的最小树找的最小树找出来出来出来出来.因此这个问题就叫做最小树问题因此这个问题就叫做最小树问题因此这个问题就叫做最小树问题因此这个问题就叫做最小树问题.最小树问题有很多很广泛的应用最小树问题有很多很广泛的应用最小树问题有很多很广泛的应用最小树问题有很多很广泛的应用.例如，我们把例如，我们把例如，我们把例如，我们把图图图图5.1.3(a)5.1.3(a)5.1.3(a)5.1.3(a)的图
10、的图的图的图G G G G中的五个顶点看成某个镇的中的五个顶点看成某个镇的中的五个顶点看成某个镇的中的五个顶点看成某个镇的5 5 5 5个村，个村，个村，个村，G G G G的边看成是马路，现在要假设电线的边看成是马路，现在要假设电线的边看成是马路，现在要假设电线的边看成是马路，现在要假设电线(电线必需沿着马电线必需沿着马电线必需沿着马电线必需沿着马路假设路假设路假设路假设)，使各村之间都能通电话，使各村之间都能通电话，使各村之间都能通电话，使各村之间都能通电话,问应当怎样架线，问应当怎样架线，问应当怎样架线，问应当怎样架线，才能使所用的电线最少？才能使所用的电线最少？才能使所用的电线最少？才
11、能使所用的电线最少？考虑一下，就可以看出，这个问题的关键是确定图考虑一下，就可以看出，这个问题的关键是确定图考虑一下，就可以看出，这个问题的关键是确定图考虑一下，就可以看出，这个问题的关键是确定图上哪些边上架线，哪些边上不架线上哪些边上架线，哪些边上不架线上哪些边上架线，哪些边上不架线上哪些边上架线，哪些边上不架线.设架线的边的集合设架线的边的集合设架线的边的集合设架线的边的集合是是是是E1,E1,E1,E1,那么那么那么那么G1=(V,E1)G1=(V,E1)G1=(V,E1)G1=(V,E1)就是就是就是就是G G G G的一个支撑子图的一个支撑子图的一个支撑子图的一个支撑子图.因为架线后
12、因为架线后因为架线后因为架线后各个村之间都能通话，所以各个村之间都能通话，所以各个村之间都能通话，所以各个村之间都能通话，所以G1G1G1G1必需是连通的必需是连通的必需是连通的必需是连通的.因此要使因此要使因此要使因此要使电线最节约，就是要从电线最节约，就是要从电线最节约，就是要从电线最节约，就是要从G G G G的全部连通的支撑子图中，把的全部连通的支撑子图中，把的全部连通的支撑子图中，把的全部连通的支撑子图中，把总边长最小的找出来，但是不难看出，总边长最小的连总边长最小的找出来，但是不难看出，总边长最小的连总边长最小的找出来，但是不难看出，总边长最小的连总边长最小的找出来，但是不难看出，
13、总边长最小的连通支撑子图确定不会含圈，从而必定是一个支撑树通支撑子图确定不会含圈，从而必定是一个支撑树通支撑子图确定不会含圈，从而必定是一个支撑树通支撑子图确定不会含圈，从而必定是一个支撑树.因因因因此假设电线的问题就归结为最小树问题此假设电线的问题就归结为最小树问题此假设电线的问题就归结为最小树问题此假设电线的问题就归结为最小树问题.类似的问题还有很多，例如修马路把一些城镇连类似的问题还有很多，例如修马路把一些城镇连类似的问题还有很多，例如修马路把一些城镇连类似的问题还有很多，例如修马路把一些城镇连接起来，修渠道使水源和各块地连接起来，等等，都接起来，修渠道使水源和各块地连接起来，等等，都接
14、起来，修渠道使水源和各块地连接起来，等等，都接起来，修渠道使水源和各块地连接起来，等等，都可以归结为最小树问题可以归结为最小树问题可以归结为最小树问题可以归结为最小树问题.同时，最小树问题还是图论同时，最小树问题还是图论同时，最小树问题还是图论同时，最小树问题还是图论中其它很多问题的基础，也就是说，有不少的问题在中其它很多问题的基础，也就是说，有不少的问题在中其它很多问题的基础，也就是说，有不少的问题在中其它很多问题的基础，也就是说，有不少的问题在计算时，往往首先必需求出一个最小树，这也是最小计算时，往往首先必需求出一个最小树，这也是最小计算时，往往首先必需求出一个最小树，这也是最小计算时，往
15、往首先必需求出一个最小树，这也是最小树问题显得特殊重要的一个缘由树问题显得特殊重要的一个缘由树问题显得特殊重要的一个缘由树问题显得特殊重要的一个缘由.本节我们来看看关于树的一些等价定义本节我们来看看关于树的一些等价定义.定理定理5.2.1 设设T=(V,E)是一个树，设是一个树，设T有有m条边，条边，n个个顶点，则顶点，则m=n-1.5.2 树的等价定义树的等价定义 在证明这个定理之前，我们先看一些引理在证明这个定理之前，我们先看一些引理.引理引理 5.2.1 设设G=(V,E)是一个图，它的每一个顶点的是一个图，它的每一个顶点的度数都满足度数都满足deg(vi)2，那么，那么G确定有圈确定有
16、圈.证明：证明的方法是：从随意一证明：证明的方法是：从随意一个顶点起先，来构造个顶点起先，来构造G的一条简洁的一条简洁了了p，起先时，起先时，p只含一个顶点，以只含一个顶点，以后逐步扩大，然后证明，扩大若干后逐步扩大，然后证明，扩大若干次后，次后，p中确定会出现圈中确定会出现圈,当然，这当然，这就证明白就证明白G中确定有圈中确定有圈.我们结合图我们结合图5.2.1来证明来证明.v v1 1v v3 3v v2 2v v4 4v v5 5e e1 1e e3 3e e4 4e e5 5e e6 6e e2 2图图图图5.2.15.2.1 这个图的每个顶点的度数都大这个图的每个顶点的度数都大这个图
17、的每个顶点的度数都大这个图的每个顶点的度数都大于等于于等于于等于于等于2.2.2.2.先随意取一个顶点，例如先随意取一个顶点，例如先随意取一个顶点，例如先随意取一个顶点，例如取取取取v4v4v4v4，并且令，并且令，并且令，并且令p=v4.p=v4.p=v4.p=v4.因为因为因为因为deg(v4)2deg(v4)2deg(v4)2deg(v4)2，所以确定有与，所以确定有与，所以确定有与，所以确定有与v4v4v4v4关联关联关联关联的边，任取一条这样的边，例如取的边，任取一条这样的边，例如取的边，任取一条这样的边，例如取的边，任取一条这样的边，例如取e4e4e4e4，把，把，把，把e4e4e
18、4e4及它的另一个端点及它的另一个端点及它的另一个端点及它的另一个端点v2v2v2v2加到加到加到加到p p p p中去，使中去，使中去，使中去，使p p p p扩大成扩大成扩大成扩大成p=v4,e4,v2.p=v4,e4,v2.p=v4,e4,v2.p=v4,e4,v2.然然然然后再取一条与后再取一条与后再取一条与后再取一条与v2v2v2v2关联，而不属于关联，而不属于关联，而不属于关联，而不属于p p p p的的的的边边边边.因为因为因为因为deg(v2)2deg(v2)2deg(v2)2deg(v2)2，这样的边是一，这样的边是一，这样的边是一，这样的边是一v v1 1v v3 3v v
19、2 2v v4 4v v5 5e e1 1e e3 3e e4 4e e5 5e e6 6e e2 2图图图图5.2.15.2.1定存在的，例如可以取定存在的，例如可以取定存在的，例如可以取定存在的，例如可以取e1e1e1e1，把，把，把，把e1e1e1e1及它的另一个端点及它的另一个端点及它的另一个端点及它的另一个端点v1v1v1v1再加入再加入再加入再加入p p p p，使，使，使，使p p p p扩大成扩大成扩大成扩大成p=v4,e4,v2,e1,v1p=v4,e4,v2,e1,v1p=v4,e4,v2,e1,v1p=v4,e4,v2,e1,v1，这样，这样，这样，这样做下去，做下去，做
20、下去，做下去，p p p p中每增加一条边中每增加一条边中每增加一条边中每增加一条边ejejejej与一个顶点与一个顶点与一个顶点与一个顶点vivivivi后，后，后，后，就应当看一看，它属于下面两种状况中的哪一种：就应当看一看，它属于下面两种状况中的哪一种：就应当看一看，它属于下面两种状况中的哪一种：就应当看一看，它属于下面两种状况中的哪一种：状况状况状况状况1 1 1 1：vivivivi是第一次出现在是第一次出现在是第一次出现在是第一次出现在p p p p中中中中.这时，因为这时，因为这时，因为这时，因为deg(vi)2deg(vi)2deg(vi)2deg(vi)2，所以确定还有与，所
21、以确定还有与，所以确定还有与，所以确定还有与vivivivi关联而不属于关联而不属于关联而不属于关联而不属于p p p p的边，的边，的边，的边，取一条这样的边，把它及它的不同于取一条这样的边，把它及它的不同于取一条这样的边，把它及它的不同于取一条这样的边，把它及它的不同于vivivivi的另一个端点的另一个端点的另一个端点的另一个端点加入加入加入加入p p p p，p p p p就可以扩大了就可以扩大了就可以扩大了就可以扩大了.状况状况状况状况2 2 2 2：vivivivi是其次次出现在是其次次出现在是其次次出现在是其次次出现在p p p p中中中中.这时不必再扩大这时不必再扩大这时不必再
22、扩大这时不必再扩大p p p p了了了了.因为因为因为因为p p p p中从上一次出现中从上一次出现中从上一次出现中从上一次出现vivivivi到这次出现到这次出现到这次出现到这次出现vivivivi中的一段中的一段中的一段中的一段就是一个圈就是一个圈就是一个圈就是一个圈.因此，只要状况因此，只要状况因此，只要状况因此，只要状况2 2 2 2一出现，就找到圈了一出现，就找到圈了一出现，就找到圈了一出现，就找到圈了.那么，状况那么，状况那么，状况那么，状况2 2 2 2是不是确定会出现呢？确定会的是不是确定会出现呢？确定会的是不是确定会出现呢？确定会的是不是确定会出现呢？确定会的.这是因为这是因
23、为这是因为这是因为p p p p是简洁路是简洁路是简洁路是简洁路,即即即即每一条边在每一条边在每一条边在每一条边在p p p p中只出现一次，而图的总边数是有限的，因中只出现一次，而图的总边数是有限的，因中只出现一次，而图的总边数是有限的，因中只出现一次，而图的总边数是有限的，因此，此，此，此，p p p p不能无限的扩大不能无限的扩大不能无限的扩大不能无限的扩大.要是在扩大要是在扩大要是在扩大要是在扩大p p p p的过程中只是出现状的过程中只是出现状的过程中只是出现状的过程中只是出现状况况况况1 1 1 1，那么，那么，那么，那么p p p p久可以不断地扩大下去久可以不断地扩大下去久可以
24、不断地扩大下去久可以不断地扩大下去.这个冲突说明，经过这个冲突说明，经过这个冲突说明，经过这个冲突说明，经过若干次扩大后若干次扩大后若干次扩大后若干次扩大后,确定会出现状况确定会出现状况确定会出现状况确定会出现状况2.2.2.2.例如，前面已扩大到例如，前面已扩大到例如，前面已扩大到例如，前面已扩大到p=v4,e4,v2,e1,v1p=v4,e4,v2,e1,v1p=v4,e4,v2,e1,v1p=v4,e4,v2,e1,v1了了了了.看一下看一下看一下看一下v1v1v1v1，因为，因为，因为，因为v1v1v1v1是第一次出现在是第一次出现在是第一次出现在是第一次出现在p p p p中，属于中
25、，属于中，属于中，属于状况状况状况状况1 1 1 1，故可以接着扩大，例如可以，故可以接着扩大，例如可以，故可以接着扩大，例如可以，故可以接着扩大，例如可以把把把把e2e2e2e2与与与与v3v3v3v3加到加到加到加到p p p p中去中去中去中去.再看再看再看再看v3v3v3v3，仍是，仍是，仍是，仍是第一次出现，再扩大第一次出现，再扩大第一次出现，再扩大第一次出现，再扩大p p p p，例如取，例如取，例如取，例如取e3e3e3e3与与与与v2v2v2v2，即扩大成：，即扩大成：，即扩大成：，即扩大成：v v1 1v v3 3v v2 2v v4 4v v5 5e e1 1e e3 3e
26、 e4 4e e5 5e e6 6e e2 2图图图图5.2.15.2.1p=vp=vp=vp=v4 4 4 4,e,e,e,e4 4 4 4,v,v,v,v2 2 2 2,e,e,e,e1 1 1 1,v,v,v,v1 1 1 1,e,e,e,e2 2 2 2,v,v,v,v3 3 3 3,e,e,e,e3 3 3 3,v,v,v,v2 2 2 2 检查检查检查检查v2,v2v2,v2v2,v2v2,v2是其次次出现，这属于状况是其次次出现，这属于状况是其次次出现，这属于状况是其次次出现，这属于状况2 2 2 2，故不必，故不必，故不必，故不必再扩大了，因为再扩大了，因为再扩大了，因为再扩大
27、了，因为p p p p中已出现了圈中已出现了圈中已出现了圈中已出现了圈vvvv2 2 2 2,e,e,e,e1 1 1 1,v,v,v,v1 1 1 1,e,e,e,e2 2 2 2,v,v,v,v3 3 3 3,e,e,e,e3 3 3 3,v,v,v,v2 2 2 2.证毕证毕证毕证毕 引理5.2.2 设T=(V,E)为一个树，并且T至少有两个顶点，那么T确定有树叶.证明：因为T是树，所以T是连通的，T不会有孤立顶点，即每一个顶点vi的度数deg(vi)0.假如T没有树叶，即T的每个顶点的度数都大于等于2，那么，由引理5.2.1知，T含有圈，这就与T是树冲突.证毕.有了这些引理，下面可以来
28、证明定理了有了这些引理，下面可以来证明定理了.定理定理5.2.1 设设T=(V,E)是一个树，设是一个树，设T有有m条边，条边，n个个顶点，则顶点，则m=n-1.证明：设T=(V,E)是树，假如T只有两个顶点，定理明显成立，现设T有不止两个顶点.由引理5.2.2知，T有树叶.设vi是一个树叶，依据树叶的定义,应只有一条边与vi关联,设这条边是ej,不难看出,由于T中有不止两个顶点,从T中去掉vi与ej,剩下的仍是一个树T1.因为T1的边数和顶点数比G的边数和顶点数都小1.所以只要能够证明T1的边数比顶点数少1，也就证明白T的边数比顶点数少1,从而也就证明白定理.同样同样,因为因为T1是树是树,
29、T1也确定有树叶也确定有树叶.假如假如T1的顶点数的顶点数2,则再去掉一个树叶和与它关联的唯一的边可以得到树则再去掉一个树叶和与它关联的唯一的边可以得到树T2,而且只要能证明而且只要能证明T2的边数比顶点数少的边数比顶点数少1,就能证明就能证明T1,从而从而T的边数比顶点数少的边数比顶点数少1了了,这样不断的去掉树叶这样不断的去掉树叶和边和边,始终得到一个只含两个顶点的树始终得到一个只含两个顶点的树T为止为止.明显明显,T恰含一条边恰含一条边,因此因此T的边数比顶点数少的边数比顶点数少1了，倒退回去，了，倒退回去，就可以证明就可以证明T的边数比顶点数少的边数比顶点数少1了了.证毕证毕.重要的是
30、，我们还可以证明：重要的是，我们还可以证明：重要的是，我们还可以证明：重要的是，我们还可以证明：定理定理定理定理5.2.2 5.2.2 设图设图设图设图GG是连通的，并且边数比顶点数少是连通的，并且边数比顶点数少是连通的，并且边数比顶点数少是连通的，并且边数比顶点数少1 1，那么，那么，那么，那么GG是树是树是树是树.定理定理定理定理5.2.3 5.2.3 设图设图设图设图GG没有圈，并且边数等于顶点数减没有圈，并且边数等于顶点数减没有圈，并且边数等于顶点数减没有圈，并且边数等于顶点数减1 1，则，则，则，则GG是树是树是树是树.上面三个定理合在一起，可以简洁的说成：对于上面三个定理合在一起，
31、可以简洁的说成：对于上面三个定理合在一起，可以简洁的说成：对于上面三个定理合在一起，可以简洁的说成：对于一个图来说，下面三特性质只要有两个成立，第三个一个图来说，下面三特性质只要有两个成立，第三个一个图来说，下面三特性质只要有两个成立，第三个一个图来说，下面三特性质只要有两个成立，第三个也确定成立也确定成立也确定成立也确定成立.(1)(1)(1)(1)连通连通连通连通.(2)(2)(2)(2)没有圈没有圈没有圈没有圈.(3)(3)(3)(3)边数等于顶点数减边数等于顶点数减边数等于顶点数减边数等于顶点数减1.1.1.1.在树的定义中，我们把具有上述性质(1)(2)的图叫做树，在证明白前面几个定
32、理以后，我们就可以把树定义为具有性质(1)(3)或具有性质(2)(3)的图了.也就是说，树这个概念可以有三种不同的方法来下定义.这三种定义当然本质上是一样的，在数学中，一般称之为等价的定义.上面讲的树的等价定义，在求最小树时是很有用的上面讲的树的等价定义，在求最小树时是很有用的.例如下一节讲的一个计算方法，求出的是满足例如下一节讲的一个计算方法，求出的是满足(2)(3)的的支撑子图，由于树的等价定义，就可以确定它是一个支支撑子图，由于树的等价定义，就可以确定它是一个支撑树了撑树了.求连通图的最小树的方法很多，我们只讲其中的两求连通图的最小树的方法很多，我们只讲其中的两种种.第一种叫做破圈法第一
33、种叫做破圈法.这个方法可以用一句口诀来概括，这个方法可以用一句口诀来概括，就是：就是：任取一个圈，去掉圈上最长的边任取一个圈，去掉圈上最长的边.5.3 求最小树的两种计算方法求最小树的两种计算方法 我们通过一个例子把这句口诀的用法说明一下我们通过一个例子把这句口诀的用法说明一下.就就拿图拿图5.3.15.3.1中连通图为例。中连通图为例。v1v5v4v3v25286365图5.3.1 G G有好几个圈，现在任取一个，例如就取：有好几个圈，现在任取一个，例如就取：P P1 1=v=v1 1,v,v2 2,v,v4 4,v,v1 1.这个圈上有三条边，最长的是这个圈上有三条边，最长的是(v1,v4
34、),长度是长度是5，我们就，我们就把这条边去掉，从而也就把把这条边去掉，从而也就把p1破掉了破掉了.v1v5v4v3v25286365v1v5v4v3v25286365p1 接下去接下去,再看看剩下的图中还有没有圈再看看剩下的图中还有没有圈.假如没有假如没有,那么计算就结束了；假如有，就再随意取一个圈，再去那么计算就结束了；假如有，就再随意取一个圈，再去掉圈上的最长边，把这个圈破掉，直到剩下的图上没掉圈上的最长边，把这个圈破掉，直到剩下的图上没有圈有圈(或图上的边数等于顶点数减或图上的边数等于顶点数减1)1)时为止时为止.v1v5v4v3v25286365p1v1v5v4v3v2286365v
35、1v5v4v3v228365v1v5v4v3v22365 再介绍一种求最小树的方法，叫做加边法再介绍一种求最小树的方法，叫做加边法.它与破它与破圈法的做法正好相反圈法的做法正好相反.破圈法是从原来的图中逐步去掉破圈法是从原来的图中逐步去掉边，每次删边的时候，要保持住图的连通性边，每次删边的时候，要保持住图的连通性(从圈上去从圈上去掉边，余下的图确定照旧是连通的掉边，余下的图确定照旧是连通的)，直到图中没有圈，直到图中没有圈为止为止.加边法正好相反，它一起先先把图中的边去掉，加边法正好相反，它一起先先把图中的边去掉，只留下孤立的顶点，然后逐步的把边加上去，每次加的只留下孤立的顶点，然后逐步的把边
36、加上去，每次加的时候，要保持住时候，要保持住“没有圈没有圈”这一性质，在加了这一性质，在加了n-1n-1条边条边(n(n是顶点个数是顶点个数)后，就得到要求的最小树了后，就得到要求的最小树了.加边法的具体步骤是：加边法的具体步骤是：步骤步骤1 1 把图把图G G的的m m条边按从短到长的次序重新编号条边按从短到长的次序重新编号,即把最短的边叫做即把最短的边叫做e e1 1,次短的边叫做次短的边叫做e e2 2,最长的叫做最长的叫做e em m.加边法的计算框图：加边法的计算框图：步骤步骤2 2 首先把图首先把图G G的边都去掉，得到一个只含的边都去掉，得到一个只含n n个孤个孤立点的支撑子图立
37、点的支撑子图.然后，按然后，按e1,e2,eme1,e2,em的次序试着向支的次序试着向支撑子图中加边撑子图中加边.对于每一条边对于每一条边ejej，要先看一看它是否和已，要先看一看它是否和已经加进去的边形成圈经加进去的边形成圈.假如不形成圈，就把假如不形成圈，就把ejej加进去，假加进去，假如形成圈，如形成圈，ejej就不能加进去，而考虑下一条边就不能加进去，而考虑下一条边ej+1,ej+1,始终始终加到得到的支撑子图含有加到得到的支撑子图含有n-1n-1条边时，计算结束条边时，计算结束.起先：对起先：对起先：对起先：对GG的边重新编号，使的边重新编号，使的边重新编号，使的边重新编号，使l(
38、e1)l(e2)l(em)l(e1)l(e2)l(em)令支撑子图的边集合令支撑子图的边集合令支撑子图的边集合令支撑子图的边集合E E=，令，令，令，令i=1i=1e ei i加到加到加到加到E E 中去是否形成圈？中去是否形成圈？中去是否形成圈？中去是否形成圈？计算结束计算结束计算结束计算结束把把把把e ei i加到加到加到加到E E 中去中去中去中去E E 中的边数是否等于中的边数是否等于中的边数是否等于中的边数是否等于n-1n-1是是是是否否否否令令令令i=i+1i=i+1是是是是否否否否令令令令i=i+1i=i+1例例1 1、城市公交网、城市公交网 问题描述问题描述 有有一一张张城城市
39、市地地图图，图图中中的的顶顶点点为为城城市市，无无向向边边代代表表两两个个城城市市间间的的连连通通关关系系，边边上上的的权权为为在在这这两两个个城城市市之之间间修修建建高高速速马马路路的的造造价价，探探讨讨后后发发觉觉，这这个个地地图图有有一一个个特特点点，即即任任一一对对城城市市都都是是连连通通的的。现现在在的的问问题题是是，要要修修建建若若干干高高速速马马路路把把全全部部城城市市联联系系起起来来，问问如如何何设设计可使得工程的总造价最少。计可使得工程的总造价最少。5.4 应用应用 举例举例 下面的图表示一个下面的图表示一个5 5个城市的地图，可以得到它个城市的地图，可以得到它的最小生成树的
40、权和为的最小生成树的权和为19.19.例例2 2、最优布线问题（、最优布线问题（wire.?wire.?）学学校校有有n n台台计计算算机机，为为了了便便利利数数据据传传输输，现现要要将将它它们们用用数数据据线线连连接接起起来来.两两台台计计算算机机被被连连接接是是指指它它们们之之间间有有数数据据线线连连接接.由由于于计计算算机机所所处处的的位位置置不不同同，因因此此不不同同的的两两台台计算机的连接费用往往是不同的计算机的连接费用往往是不同的.当当然然，假假如如将将随随意意两两台台计计算算机机都都用用数数据据线线连连接接，费费用用将将是是相相当当浩浩大大的的.为为了了节节约约费费用用，我我们们
41、接接受受数数据据的的间间接接传传输输手手段段，即即一一台台计计算算机机可可以以间间接接的的通通过过若若干干台台计计算算机机（作为中转）来实现与另一台计算机的连接（作为中转）来实现与另一台计算机的连接.现现在在由由你你负负责责连连接接这这些些计计算算机机，你你的的任任务务是是使使随随意意两台计算机都连通（不管是干脆的或间接的）两台计算机都连通（不管是干脆的或间接的）.在要求费用最少的状况下，如何连接？在要求费用最少的状况下，如何连接？例3 机器蛇 在将来的某次斗争中,我军支配了一次军事行动，目的是劫持敌人的航母由于这个支配高度保密，你只知道你所负责的一部分：机器蛇的通信网络.支配中要将数百条机器蛇投放到航母的各个角落里由于航母内部舱室、管线错综困难，且大部分由金属构成，因此屏蔽效应特殊猛烈，况且还要考虑敌人的大强度电子干扰，如何保持机器蛇间的联系，成了一大难题.每条机器蛇的战斗位置由作战支配部门制定，将会刚好通知你每条机器蛇上都带有接收、放射系统，可以同时与多条机器蛇通讯由于整个系统承载的数据量浩大，须要一个固定的通讯网络情报部门供应了极其详尽的敌方航母图纸，使你对什么地方有屏蔽了如指掌 请你设计一个程序，依据以上信息构造通讯网络,要求信息可以在随意两条机器蛇间传递，同时为了避开干扰，通讯网络的总长度要尽可能的短