教学课件：第五章-最小树问题.ppt

《教学课件：第五章-最小树问题.ppt》由会员分享，可在线阅读，更多相关《教学课件：第五章-最小树问题.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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=(V,E)G=(V,E)G=(V,E)的支撑子图，指的的支撑子图，指的的支撑子图，指的的支撑子图，指的是是是是G G G G的一个子图的一

3、个子图的一个子图的一个子图G G G G1 1 1 1=(V=(V=(V=(V1 1 1 1,E,E,E,E1 1 1 1)，其中，其中，其中，其中V V V V1 1 1 1=V=V=V=V，即，即，即，即G G G G1 1 1 1是由是由是由是由G G G G的全的全的全的全部顶点及一部分边组成的部顶点及一部分边组成的部顶点及一部分边组成的部顶点及一部分边组成的.对于我们来说，特别重要对于我们来说，特别重要对于我们来说，特别重要对于我们来说，特别重要的是图的是图的是图的是图G(GG(GG(GG(G本身不一定是树本身不一定是树本身不一定是树本身不一定是树)的那些形成树的支撑子图的那些形成树

4、的支撑子图的那些形成树的支撑子图的那些形成树的支撑子图.定义定义定义定义5.1.2 5.1.2 5.1.2 5.1.2 设设设设G=(V,E)G=(V,E)G=(V,E)G=(V,E)是一个无向图，如果是一个无向图，如果是一个无向图，如果是一个无向图，如果T=(V,ET=(V,ET=(V,ET=(V,E1 1 1 1)是是是是G G G G的支撑子图并且的支撑子图并且的支撑子图并且的支撑子图并且T T T T是树，则称是树，则称是树，则称是树，则称T T T T是是是是G G G G的一个的一个的一个的一个支撑树支撑树支撑树支撑树.图图图图 是不是每个图是不是每个图是不是每个图是不是每个图G

5、G G G都有支撑树呢？不见得都有支撑树呢？不见得都有支撑树呢？不见得都有支撑树呢？不见得.很显然，很显然，很显然，很显然，如果如果如果如果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

6、G没有圈，那么没有圈，那么没有圈，那么没有圈，那么G G G G本身就是一个支撑树，如果本身就是一个支撑树，如果本身就是一个支撑树，如果本身就是一个支撑树，如果G G G G有圈，那么任取有圈，那么任取有圈，那么任取有圈，那么任取G G G G的一个的一个的一个的一个圈，并且从这个圈中任意去掉一条边，得到圈，并且从这个圈中任意去掉一条边，得到圈，并且从这个圈中任意去掉一条边，得到圈，并且从这个圈中任意去掉一条边，得到G G G G的一个的一个的一个的一个支撑子图支撑子图支撑子图支撑子图G G G G1 1 1 1,易见易见易见易见G G G G1 1 1 1仍是连通的，如果仍是连通的，如果仍是

7、连通的，如果仍是连通的，如果G G G G1 1 1 1还有圈，就再还有圈，就再还有圈，就再还有圈，就再从某一个圈中去掉一条边，得到从某一个圈中去掉一条边，得到从某一个圈中去掉一条边，得到从某一个圈中去掉一条边，得到G G G G2 2 2 2，G G G G2 2 2 2仍是连通的，仍是连通的，仍是连通的，仍是连通的，这样做下去，直至得到一个不含圈的连通支撑子，这样做下去，直至得到一个不含圈的连通支撑子，这样做下去，直至得到一个不含圈的连通支撑子，这样做下去，直至得到一个不含圈的连通支撑子图图图图G G G Gs s s s为止，为止，为止，为止，G G G Gs s s s就是就是就是就是

8、G G G G的一个支撑树了的一个支撑树了的一个支撑树了的一个支撑树了.按定理的证明方法得到一个支撑树的过程成为按定理的证明方法得到一个支撑树的过程成为按定理的证明方法得到一个支撑树的过程成为按定理的证明方法得到一个支撑树的过程成为“破圈法破圈法破圈法破圈法”。从破圈的过程可以看出，一个连通图从破圈的过程可以看出，一个连通图从破圈的过程可以看出，一个连通图从破圈的过程可以看出，一个连通图G G G G一般有许多一般有许多一般有许多一般有许多支撑树支撑树支撑树支撑树.因为取定一个圈后，可以从这个圈上任意去因为取定一个圈后，可以从这个圈上任意去因为取定一个圈后，可以从这个圈上任意去因为取定一个圈后

9、，可以从这个圈上任意去掉一条边掉一条边掉一条边掉一条边.去掉的边不一样，得到的支撑树就不同去掉的边不一样，得到的支撑树就不同去掉的边不一样，得到的支撑树就不同去掉的边不一样，得到的支撑树就不同.现在考虑一个连通图现在考虑一个连通图现在考虑一个连通图现在考虑一个连通图G=(V,E)G=(V,E)G=(V,E)G=(V,E)，它的每一条边，它的每一条边，它的每一条边，它的每一条边e e e ej j j j有有有有一个长度一个长度一个长度一个长度l(el(el(el(ej j j j)0.)0.)0.)0.这时，对于这时，对于这时，对于这时，对于G G G G的任意一个支撑树的任意一个支撑树的任意

10、一个支撑树的任意一个支撑树T T T T，我们把属于我们把属于我们把属于我们把属于T T T T的各条边的长度加起来的和叫做树的各条边的长度加起来的和叫做树的各条边的长度加起来的和叫做树的各条边的长度加起来的和叫做树T T T T的长的长的长的长度，记作度，记作度，记作度，记作l(T).l(T).l(T).l(T).如下图：如下图：如下图：如下图：l(Tl(Tl(Tl(T1 1 1 1)=22,l(T)=22,l(T)=22,l(T)=22,l(T2 2 2 2)=17.)=17.)=17.)=17.v v1 1v v2 2v v3 3v v4 4v v5 55 58 86 62 23 36

11、65 5v v1 1v v2 2v v3 3v 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的所有支撑树中，把长度最的所有支撑树中，把长度最的所有支撑树中，把长度最的所有支撑树中，把长度最小的支撑树找出来？小的支撑树找出来？小的支撑树找出来？小的支撑树找出来？.通常，我们把长度最小的支撑树叫做最小树通常，我们把长度最小的支撑树叫做最小

12、树通常，我们把长度最小的支撑树叫做最小树通常，我们把长度最小的支撑树叫做最小树.所所所所以上面的问题实际上就是如何把一个图以上面的问题实际上就是如何把一个图以上面的问题实际上就是如何把一个图以上面的问题实际上就是如何把一个图G G G G的最小树找的最小树找的最小树找的最小树找出来出来出来出来.因此这个问题就叫做最小树问题因此这个问题就叫做最小树问题因此这个问题就叫做最小树问题因此这个问题就叫做最小树问题.最小树问题有很多很广泛的应用最小树问题有很多很广泛的应用最小树问题有很多很广泛的应用最小树问题有很多很广泛的应用.例如，我们把例如，我们把例如，我们把例如，我们把图图图图5.1.3(a)5.

13、1.3(a)5.1.3(a)5.1.3(a)的图的图的图的图G G G G中的五个顶点看成某个镇的中的五个顶点看成某个镇的中的五个顶点看成某个镇的中的五个顶点看成某个镇的5 5 5 5个村，个村，个村，个村，G G G G的边看成是公路，现在要假设电线的边看成是公路，现在要假设电线的边看成是公路，现在要假设电线的边看成是公路，现在要假设电线(电线必须沿着公电线必须沿着公电线必须沿着公电线必须沿着公路假设路假设路假设路假设)，使各村之间都能通电话，使各村之间都能通电话，使各村之间都能通电话，使各村之间都能通电话,问应该怎样架线，问应该怎样架线，问应该怎样架线，问应该怎样架线，才能使所用的电线最少

14、？才能使所用的电线最少？才能使所用的电线最少？才能使所用的电线最少？考虑一下，就可以看出，这个问题的关键是决定图考虑一下，就可以看出，这个问题的关键是决定图考虑一下，就可以看出，这个问题的关键是决定图考虑一下，就可以看出，这个问题的关键是决定图上哪些边上架线，哪些边上不架线上哪些边上架线，哪些边上不架线上哪些边上架线，哪些边上不架线上哪些边上架线，哪些边上不架线.设架线的边的集合设架线的边的集合设架线的边的集合设架线的边的集合是是是是E E E E1 1 1 1,那么那么那么那么G G G G1 1 1 1=(V,E=(V,E=(V,E=(V,E1 1 1 1)就是就是就是就是G G G G的

15、一个支撑子图的一个支撑子图的一个支撑子图的一个支撑子图.因为架线后因为架线后因为架线后因为架线后各个村之间都能通话，所以各个村之间都能通话，所以各个村之间都能通话，所以各个村之间都能通话，所以G G G G1 1 1 1必须是连通的必须是连通的必须是连通的必须是连通的.因此要使因此要使因此要使因此要使电线最节约，就是要从电线最节约，就是要从电线最节约，就是要从电线最节约，就是要从G G G G的所有连通的支撑子图中，把的所有连通的支撑子图中，把的所有连通的支撑子图中，把的所有连通的支撑子图中，把总边长最小的找出来，但是不难看出，总边长最小的连总边长最小的找出来，但是不难看出，总边长最小的连总边

16、长最小的找出来，但是不难看出，总边长最小的连总边长最小的找出来，但是不难看出，总边长最小的连通支撑子图一定不会含圈，从而必定是一个支撑树通支撑子图一定不会含圈，从而必定是一个支撑树通支撑子图一定不会含圈，从而必定是一个支撑树通支撑子图一定不会含圈，从而必定是一个支撑树.因因因因此假设电线的问题就归结为最小树问题此假设电线的问题就归结为最小树问题此假设电线的问题就归结为最小树问题此假设电线的问题就归结为最小树问题.类似的问题还有很多，例如修公路把一些城镇连类似的问题还有很多，例如修公路把一些城镇连类似的问题还有很多，例如修公路把一些城镇连类似的问题还有很多，例如修公路把一些城镇连接起来，修渠道使

17、水源和各块地连接起来，等等，都接起来，修渠道使水源和各块地连接起来，等等，都接起来，修渠道使水源和各块地连接起来，等等，都接起来，修渠道使水源和各块地连接起来，等等，都可以归结为最小树问题可以归结为最小树问题可以归结为最小树问题可以归结为最小树问题.同时，最小树问题还是图论同时，最小树问题还是图论同时，最小树问题还是图论同时，最小树问题还是图论中其它很多问题的基础，也就是说，有不少的问题在中其它很多问题的基础，也就是说，有不少的问题在中其它很多问题的基础，也就是说，有不少的问题在中其它很多问题的基础，也就是说，有不少的问题在计算时，往往首先必须求出一个最小树，这也是最小计算时，往往首先必须求出

18、一个最小树，这也是最小计算时，往往首先必须求出一个最小树，这也是最小计算时，往往首先必须求出一个最小树，这也是最小树问题显得特别重要的一个原因树问题显得特别重要的一个原因树问题显得特别重要的一个原因树问题显得特别重要的一个原因.本节我们来看看关于树的一些等价定义本节我们来看看关于树的一些等价定义.定理定理5.2.1 设设T=(V,E)是一个树，设是一个树，设T有有m条边，条边，n个个顶点，则顶点，则m=n-1.5.2 树的等价定义树的等价定义 在证明这个定理之前，我们先看一些引理在证明这个定理之前，我们先看一些引理.引理引理 5.2.1 设设G=(V,E)是一个图，它的每一个顶点的是一个图，它

19、的每一个顶点的度数都满足度数都满足deg(vi)2，那么，那么G一定有圈一定有圈.证明：证明的方法是：从任意一证明：证明的方法是：从任意一个顶点开始，来构造个顶点开始，来构造G的一条简单的一条简单了了p，开始时，开始时，p只含一个顶点，以只含一个顶点，以后逐步扩大，然后证明，扩大若干后逐步扩大，然后证明，扩大若干次后，次后，p中一定会出现圈中一定会出现圈,当然，这当然，这就证明了就证明了G中一定有圈中一定有圈.我们结合图我们结合图来证明来证明.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

20、.2.1 这个图的每个顶点的度数都大这个图的每个顶点的度数都大这个图的每个顶点的度数都大这个图的每个顶点的度数都大于等于于等于于等于于等于2.2.2.2.先任意取一个顶点，例如先任意取一个顶点，例如先任意取一个顶点，例如先任意取一个顶点，例如取取取取v v v v4 4 4 4，并且令，并且令，并且令，并且令p=vp=vp=vp=v4 4 4 4.因为因为因为因为deg(vdeg(vdeg(vdeg(v4 4 4 4)2 2，所以一定有与，所以一定有与，所以一定有与，所以一定有与v v v v4 4 4 4关联关联关联关联的边，任取一条这样的边，例如取的边，任取一条这样的边，例如取的边，任取一

21、条这样的边，例如取的边，任取一条这样的边，例如取e e e e4 4 4 4，把，把，把，把e e e e4 4 4 4及它的另一个端点及它的另一个端点及它的另一个端点及它的另一个端点v v v v2 2 2 2加到加到加到加到p p p p中去，使中去，使中去，使中去，使p p p p扩大成扩大成扩大成扩大成p=vp=vp=vp=v4 4 4 4,e,e,e,e4 4 4 4,v,v,v,v2 2 2 2.然后然后然后然后再取一条与再取一条与再取一条与再取一条与v v v v2 2 2 2关联，而不属于关联，而不属于关联，而不属于关联，而不属于p p p p的边的边的边的边.因为因为因为因为

22、deg(vdeg(vdeg(vdeg(v2 2 2 2)2 2，这样的边是一，这样的边是一，这样的边是一，这样的边是一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定存在的，例如可以取定存在的，例如可以取定存在的，例如可以取定存在的，例如可以取e e e e1 1 1 1，把，把，把，把e e e e1 1 1 1及它的另一个端点及它的另一个端点及它的另一个端点及它的另一个端点v v v v1 1 1 1再加入再加入再加入再加入p p p p，使，使，使，使p p p p扩大成扩大

23、成扩大成扩大成p=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 ，这样做，这样做，这样做，这样做下去，下去，下去，下去，p p p p中每增加一条边中每增加一条边中每增加一条边中每增加一条边e e e ej j j j 与一个顶点与一个顶点与一个顶点与一个顶点v v v vi i i i 后，就应后，就应后，就应后，就应该看一看，它属于下面两种情况中的哪一种：该看一看，它属于下面两种情况中的哪一种：该看一看，它属于下面两种情况中的哪一种：该看一看，它属于下面两种情况中的哪一种：情况情况

24、情况情况1 1 1 1：v v v vi i i i 是第一次出现在是第一次出现在是第一次出现在是第一次出现在p p p p中中中中.这时，因为这时，因为这时，因为这时，因为deg(vdeg(vdeg(vdeg(vi i i i)2 2，所以一定还有与，所以一定还有与，所以一定还有与，所以一定还有与v v v vi i i i 关联而不属于关联而不属于关联而不属于关联而不属于p p p p的边，取的边，取的边，取的边，取一条这样的边，把它及它的不同于一条这样的边，把它及它的不同于一条这样的边，把它及它的不同于一条这样的边，把它及它的不同于v vi i 的另一个端点加入的另一个端点加入的另一个端

25、点加入的另一个端点加入p p p p，p p p p就可以扩大了就可以扩大了就可以扩大了就可以扩大了.情况情况情况情况2 2 2 2：v v v vi i i i 是第二次出现在是第二次出现在是第二次出现在是第二次出现在p p p p中中中中.这时不必再扩大这时不必再扩大这时不必再扩大这时不必再扩大p p p p了了了了.因为因为因为因为p p p p中从上一次出现中从上一次出现中从上一次出现中从上一次出现v v v vi i i i 到这次出现到这次出现到这次出现到这次出现v vi i 中的一段就中的一段就中的一段就中的一段就是一个圈是一个圈是一个圈是一个圈.因此，只要情况因此，只要情况因此

26、，只要情况因此，只要情况2 2 2 2一出现，就找到圈了一出现，就找到圈了一出现，就找到圈了一出现，就找到圈了.那么，情况那么，情况那么，情况那么，情况2 2 2 2是不是一定会出现呢？一定会的是不是一定会出现呢？一定会的是不是一定会出现呢？一定会的是不是一定会出现呢？一定会的.这是因为这是因为这是因为这是因为p p p p是简单路是简单路是简单路是简单路,即即即即每一条边在每一条边在每一条边在每一条边在p p p p中只出现一次，而图的总边数是有限的，因中只出现一次，而图的总边数是有限的，因中只出现一次，而图的总边数是有限的，因中只出现一次，而图的总边数是有限的，因此，此，此，此，p p p

27、 p不能无限的扩大不能无限的扩大不能无限的扩大不能无限的扩大.要是在扩大要是在扩大要是在扩大要是在扩大p p p p的过程中只是出现情的过程中只是出现情的过程中只是出现情的过程中只是出现情况况况况1 1 1 1，那么，那么，那么，那么p p p p久可以不断地扩大下去久可以不断地扩大下去久可以不断地扩大下去久可以不断地扩大下去.这个矛盾说明，经过这个矛盾说明，经过这个矛盾说明，经过这个矛盾说明，经过若干次扩大后若干次扩大后若干次扩大后若干次扩大后,一定会出现情况一定会出现情况一定会出现情况一定会出现情况2.2.2.2.例如，前面已扩大到例如，前面已扩大到例如，前面已扩大到例如，前面已扩大到p=

28、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 了了了了.看一下看一下看一下看一下v v v v1 1 1 1，因，因，因，因为为为为v v v v1 1 1 1是第一次出现在是第一次出现在是第一次出现在是第一次出现在p p p p中，属于情况中，属于情况中，属于情况中，属于情况1 1 1 1，故可以继续扩大，例如可以把，故可以继续扩大，例如可以把，故可以继续扩大，例如可以把，故可以继续扩大，例如可以把e e e e2 2 2 2与与与与v v v v3 3 3 3加到加到加到加到p p

29、 p p中去中去中去中去.再看再看再看再看v v v v3 3 3 3，仍是第一，仍是第一，仍是第一，仍是第一次出现，再扩大次出现，再扩大次出现，再扩大次出现，再扩大p p p p，例如取，例如取，例如取，例如取e e e e3 3 3 3与与与与v v v v2 2 2 2，即扩大成：即扩大成：即扩大成：即扩大成：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.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

30、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 检查检查检查检查v v v v2 2 2 2,v,v,v,v2 2 2 2是第二次出现，这属于情况是第二次出现，这属于情况是第二次出现，这属于情况是第二次出现，这属于情况2 2 2 2，故不必，故不必，故不必，故不必再扩大了，因为再扩大了，因为再扩大了，因为再扩大了，因为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

31、 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 5.2.2 5.2.2 5.2.2 设设设设T=(V,E)T=(V,E)T=(V,E)T=(V,E)为一个树，并且为一个树，并且为一个树，并且为一个树，并且T T T T至少有两至少有两至少有两至少有两个顶点，那么个顶点，那么个顶点，那么个顶点，那么T T T T一定有树叶一定有树叶一定有树叶一定有树叶.证明：因为证明：因为证明：因为证明：因为T T T T是树，所以是树，所以是树，所以是树，所以T T T T是连通的，是连通的，是连通的，是连通的，T

32、T T T不会有孤立不会有孤立不会有孤立不会有孤立顶点，即每一个顶点顶点，即每一个顶点顶点，即每一个顶点顶点，即每一个顶点v v v vi i i i的度数的度数的度数的度数deg(vdeg(vdeg(vdeg(vi i i i)0.)0.)0.)0.如果如果如果如果T T T T没有树没有树没有树没有树叶，即叶，即叶，即叶，即T T T T的每个顶点的度数都大于等于的每个顶点的度数都大于等于的每个顶点的度数都大于等于的每个顶点的度数都大于等于2 2 2 2，那么，由引，那么，由引，那么，由引，那么，由引理知，理知，理知，理知，T T T T含有圈，这就与含有圈，这就与含有圈，这就与含有圈，这

33、就与T T T T是树矛盾是树矛盾是树矛盾是树矛盾.证毕证毕证毕证毕.有了这些引理，下面可以来证明定理了有了这些引理，下面可以来证明定理了.定理定理5.2.1 设设T=(V,E)是一个树，设是一个树，设T有有m条边，条边，n个个顶点，则顶点，则m=n-1.证明：设证明：设证明：设证明：设T=(V,E)T=(V,E)T=(V,E)T=(V,E)是树，如果是树，如果是树，如果是树，如果T T T T只有两个顶点，定理只有两个顶点，定理只有两个顶点，定理只有两个顶点，定理显然成立，现设显然成立，现设显然成立，现设显然成立，现设T T T T有不止两个顶点有不止两个顶点有不止两个顶点有不止两个顶点.由

34、引理知，由引理知，由引理知，由引理知，T T T T有树叶有树叶有树叶有树叶.设设设设v v v vi i i i是一个树叶，根据树叶的定义是一个树叶，根据树叶的定义是一个树叶，根据树叶的定义是一个树叶，根据树叶的定义,应只有一条边与应只有一条边与应只有一条边与应只有一条边与v v v vi i i i关关关关联联联联,设这条边是设这条边是设这条边是设这条边是e e e ej j j j,不难看出不难看出不难看出不难看出,由于由于由于由于T T T T中有不止两个顶点中有不止两个顶点中有不止两个顶点中有不止两个顶点,从从从从T T T T中去掉中去掉中去掉中去掉v v v vi i i i与与

35、与与e e e ej j j j,剩下的仍是一个树剩下的仍是一个树剩下的仍是一个树剩下的仍是一个树T T T T1 1 1 1.因为因为因为因为T T T T1 1 1 1的边数和的边数和的边数和的边数和顶点数比顶点数比顶点数比顶点数比G G G G的边数和顶点数都小的边数和顶点数都小的边数和顶点数都小的边数和顶点数都小1.1.1.1.所以只要能够证明所以只要能够证明所以只要能够证明所以只要能够证明T T T T1 1 1 1的边数比顶点数少的边数比顶点数少的边数比顶点数少的边数比顶点数少1 1 1 1，也就证明了，也就证明了，也就证明了，也就证明了T T T T的边数比顶点数少的边数比顶点数

36、少的边数比顶点数少的边数比顶点数少1,1,1,1,从而也就证明了定理从而也就证明了定理从而也就证明了定理从而也就证明了定理.同样同样,因为因为T1是树是树,T1也一定有树叶也一定有树叶.如果如果T1的顶点数的顶点数2,则再去掉一个树叶和与它关联的唯一的边可以得到树则再去掉一个树叶和与它关联的唯一的边可以得到树T2,而且只要能证明而且只要能证明T2的边数比顶点数少的边数比顶点数少1,就能证明就能证明T1,从而从而T的边数比顶点数少的边数比顶点数少1了了,这样不断的去掉树叶和边这样不断的去掉树叶和边,一一直得到一个只含两个顶点的树直得到一个只含两个顶点的树T为止为止.显然显然,T恰含一条边恰含一条

37、边,因此因此T的边数比顶点数少的边数比顶点数少1了，倒退回去，就可以证明了，倒退回去，就可以证明T的边数比顶点数少的边数比顶点数少1了了.证毕证毕.重要的是，我们还可以证明：重要的是，我们还可以证明：重要的是，我们还可以证明：重要的是，我们还可以证明：定理定理定理定理5.2.2 5.2.2 设图设图设图设图GG是连通的，并且边数比顶点数少是连通的，并且边数比顶点数少是连通的，并且边数比顶点数少是连通的，并且边数比顶点数少1 1，那么，那么，那么，那么GG是树是树是树是树.定理定理定理定理5.2.3 5.2.3 设图设图设图设图GG没有圈，并且边数等于顶点数减没有圈，并且边数等于顶点数减没有圈，

38、并且边数等于顶点数减没有圈，并且边数等于顶点数减1 1，则，则，则，则GG是树是树是树是树.上面三个定理合在一起，可以简单的说成：对于上面三个定理合在一起，可以简单的说成：对于上面三个定理合在一起，可以简单的说成：对于上面三个定理合在一起，可以简单的说成：对于一个图来说，下面三个性质只要有两个成立，第三个一个图来说，下面三个性质只要有两个成立，第三个一个图来说，下面三个性质只要有两个成立，第三个一个图来说，下面三个性质只要有两个成立，第三个也一定成立也一定成立也一定成立也一定成立.(1)(1)(1)(1)连通连通连通连通.(2)(2)(2)(2)没有圈没有圈没有圈没有圈.(3)(3)(3)(3

39、)边数等于顶点数减边数等于顶点数减边数等于顶点数减边数等于顶点数减1.1.1.1.在树的定义中，我们把具有上述性质在树的定义中，我们把具有上述性质在树的定义中，我们把具有上述性质在树的定义中，我们把具有上述性质(1)(2)(1)(2)(1)(2)(1)(2)的图叫的图叫的图叫的图叫做树，在证明了前面几个定理以后，我们就可以把树定做树，在证明了前面几个定理以后，我们就可以把树定做树，在证明了前面几个定理以后，我们就可以把树定做树，在证明了前面几个定理以后，我们就可以把树定义为具有性质义为具有性质义为具有性质义为具有性质(1)(3)(1)(3)(1)(3)(1)(3)或具有性质或具有性质或具有性质

40、或具有性质(2)(3)(2)(3)(2)(3)(2)(3)的图了的图了的图了的图了.也就是也就是也就是也就是说，树这个概念可以有三种不同的方法来下定义说，树这个概念可以有三种不同的方法来下定义说，树这个概念可以有三种不同的方法来下定义说，树这个概念可以有三种不同的方法来下定义.这三这三这三这三种定义当然本质上是一样的，在数学中，一般称之为等种定义当然本质上是一样的，在数学中，一般称之为等种定义当然本质上是一样的，在数学中，一般称之为等种定义当然本质上是一样的，在数学中，一般称之为等价的定义价的定义价的定义价的定义.上面讲的树的等价定义，在求最小树时是很有用的上面讲的树的等价定义，在求最小树时是

41、很有用的.例如下一节讲的一个计算方法，求出的是满足例如下一节讲的一个计算方法，求出的是满足(2)(3)的支的支撑子图，由于树的等价定义，就可以肯定它是一个支撑撑子图，由于树的等价定义，就可以肯定它是一个支撑树了树了.求连通图的最小树的方法很多，我们只讲其中的两求连通图的最小树的方法很多，我们只讲其中的两种种.第一种叫做破圈法第一种叫做破圈法.这个方法可以用一句口诀来概括这个方法可以用一句口诀来概括，就是：，就是：任取一个圈，去掉圈上最长的边任取一个圈，去掉圈上最长的边.5.3 求最小树的两种计算方法求最小树的两种计算方法 我们通过一个例子把这句口诀的用法解释一下我们通过一个例子把这句口诀的用法

42、解释一下.就就拿图中连通图为例。拿图中连通图为例。v1v5v4v3v25286365图5.3.1 G G有好几个圈，现在任取一个，例如就取：有好几个圈，现在任取一个，例如就取：P P1 1=v=v1 1,v,v2 2,v,v4 4,v,v1 1.这个圈上有三条边，最长的是这个圈上有三条边，最长的是(v1,v4),长度是长度是5，我们就，我们就把这条边去掉，从而也就把把这条边去掉，从而也就把p1破掉了破掉了.v1v5v4v3v25286365v1v5v4v3v25286365p1 接下去接下去,再看看剩下的图中还有没有圈再看看剩下的图中还有没有圈.如果没有如果没有,那么计算就结束了；如果有，就再

43、任意取一个圈，再去那么计算就结束了；如果有，就再任意取一个圈，再去掉圈上的最长边，把这个圈破掉，直到剩下的图上没掉圈上的最长边，把这个圈破掉，直到剩下的图上没有圈有圈(或图上的边数等于顶点数减或图上的边数等于顶点数减1)1)时为止时为止.v1v5v4v3v25286365p1v1v5v4v3v2286365v1v5v4v3v228365v1v5v4v3v22365 再介绍一种求最小树的方法，叫做加边法再介绍一种求最小树的方法，叫做加边法.它与破它与破圈法的做法正好相反圈法的做法正好相反.破圈法是从原来的图中逐步去掉破圈法是从原来的图中逐步去掉边，每次删边的时候，要保持住图的连通性边，每次删边的

44、时候，要保持住图的连通性(从圈上去从圈上去掉边，余下的图一定仍旧是连通的掉边，余下的图一定仍旧是连通的)，直到图中没有圈，直到图中没有圈为止为止.加边法正好相反，它一开始先把图中的边去掉，加边法正好相反，它一开始先把图中的边去掉，只留下孤立的顶点，然后逐步的把边加上去，每次加的只留下孤立的顶点，然后逐步的把边加上去，每次加的时候，要保持住时候，要保持住“没有圈没有圈”这一性质，在加了这一性质，在加了n-1n-1条边条边(n(n是顶点个数是顶点个数)后，就得到要求的最小树了后，就得到要求的最小树了.加边法的具体步骤是：加边法的具体步骤是：步骤步骤1 1 把图把图G G的的m m条边按从短到长的次

45、序重新编号条边按从短到长的次序重新编号,即把最短的边叫做即把最短的边叫做e e1 1,次短的边叫做次短的边叫做e e2 2,最长的叫做最长的叫做e em m.加边法的计算框图：加边法的计算框图：步骤步骤2 2 首先把图首先把图G G的边都去掉，得到一个只含的边都去掉，得到一个只含n n个孤个孤立点的支撑子图立点的支撑子图.然后，按然后，按e e1 1,e,e2 2,e,em m的次序试着向支撑的次序试着向支撑子图中加边子图中加边.对于每一条边对于每一条边e ej j，要先看一看它是否和已经，要先看一看它是否和已经加进去的边形成圈加进去的边形成圈.如果不形成圈，就把如果不形成圈，就把e ej j

46、加进去，如果加进去，如果形成圈，形成圈，e ej j就不能加进去，而考虑下一条边就不能加进去，而考虑下一条边e ej+1j+1,一直加一直加到得到的支撑子图含有到得到的支撑子图含有n-1n-1条边时，计算结束条边时，计算结束.开始：对开始：对开始：对开始：对GG的边重新编号，使的边重新编号，使的边重新编号，使的边重新编号，使l(el(e1 1)l(el(e2 2)l(el(emm)令支撑子图的边集合令支撑子图的边集合令支撑子图的边集合令支撑子图的边集合E E=，令，令，令，令i=1i=1e ei i加到加到加到加到E E 中去是否形成圈？中去是否形成圈？中去是否形成圈？中去是否形成圈？计算结束

47、计算结束计算结束计算结束把把把把e ei i加到加到加到加到E E 中去中去中去中去E E 中的边数是否等于中的边数是否等于中的边数是否等于中的边数是否等于n-1n-1是是是是否否否否令令令令i=i+1i=i+1是是是是否否否否令令令令i=i+1i=i+1例例1 1、城市公交网、城市公交网 问题描述问题描述 有有一一张张城城市市地地图图，图图中中的的顶顶点点为为城城市市，无无向向边边代代表表两两个个城城市市间间的的连连通通关关系系，边边上上的的权权为为在在这这两两个个城城市市之之间间修修建建高高速速公公路路的的造造价价，研研究究后后发发现现，这这个个地地图图有有一一个个特特点点，即即任任一一对

48、对城城市市都都是是连连通通的的。现现在在的的问问题题是是，要要修修建建若若干干高高速速公公路路把把所所有有城城市市联联系系起起来来，问问如如何何设设计可使得工程的总造价最少。计可使得工程的总造价最少。5.4 应用应用 举例举例 下面的图表示一个下面的图表示一个5 5个城市的地图，可以得到它个城市的地图，可以得到它的最小生成树的权和为的最小生成树的权和为19.19.例例2 2、最优布线问题（、最优布线问题（wire.?wire.?）学学校校有有n n台台计计算算机机，为为了了方方便便数数据据传传输输，现现要要将将它它们们用用数数据据线线连连接接起起来来.两两台台计计算算机机被被连连接接是是指指它

49、它们们之之间间有有数数据据线线连连接接.由由于于计计算算机机所所处处的的位位置置不不同同，因因此此不不同同的的两两台台计算机的连接费用往往是不同的计算机的连接费用往往是不同的.当当然然，如如果果将将任任意意两两台台计计算算机机都都用用数数据据线线连连接接，费费用用将将是是相相当当庞庞大大的的.为为了了节节省省费费用用，我我们们采采用用数数据据的的间间接接传传输输手手段段，即即一一台台计计算算机机可可以以间间接接的的通通过过若若干干台台计计算算机机（作为中转）来实现与另一台计算机的连接（作为中转）来实现与另一台计算机的连接.现现在在由由你你负负责责连连接接这这些些计计算算机机，你你的的任任务务是

50、是使使任任意意两台计算机都连通（不管是直接的或间接的）两台计算机都连通（不管是直接的或间接的）.在要求费用最少的情况下，如何连接？在要求费用最少的情况下，如何连接？例3 机器蛇 在未来的某次战争中,我军计划了一次军事行动，目的是劫持敌人的航母由于这个计划高度保密，你只知道你所负责的一部分：机器蛇的通信网络.计划中要将数百条机器蛇投放到航母的各个角落里由于航母内部舱室、管线错综复杂，且大部分由金属构成，因此屏蔽效应十分强烈，况且还要考虑敌人的大强度电子干扰，如何保持机器蛇间的联系，成了一大难题.每条机器蛇的战斗位置由作战计划部门制定，将会及时通知你每条机器蛇上都带有接收、发射系统，可以同时与多条