定理给定图T以下关于树的定义是等价的.PPT
定理1 给定图T， 以下关于树的定义是等价的。,(1)无回路的连通图。 (2)无回路且e=v-1，其中e是边数，v是结点数。 (3)连通且e=v-1。 (4)无回路，但增加一条新边，得到一个且仅有一个回路。 (5)连通，但删去任一边后便不连通。 (6)每一对结点之间有一条且仅有一条路。,证明（1）（2） 设在图T中，当v=2时，连通无回路，T中边数e=1，因此e=v-1成立。,假设v=k-1时命题成立，当v=k时，因为无回路且连通，故至少有一条边其一个端点u的度数为1。设该边为(u,w)，删去结点u，便得到一个k-1个结点的连通无回路图T，,由归纳假设，图T的边数e=v-1=(k-1)-1，于是再将结点u以及关联边(u,w)加到图T中得到原图T，此时T的边数为 e=e+1=(k-2)+1=k-1，结点数v=v+1=(k-1)+1=k, 故e=v-1成立。,证明（2）（3） 若T不连通，并且有k个连通分枝T1,Tk(k2)因为每个分图是连通无回路，则可证：如Ti有vi个结点，viv时，Ti有vi-1条边，而 v=v1+v2+vk e=(v1-1)+(v2-1)+(vk-1)=v-k 但e=v-1，故k=1，这与假设G是不连通即k2相矛盾。,证明（3）（4） 若T连通且有v-1条边。 当v=2时，e=v-1=1, 故 T必无回路。如增加一边得到且仅得到一个回路。,设v=k-1时命题成立。 考察v=k时的情况，因为T是连通的，e=v-1。故每个结点u有deg(u)1，可以证明至少有一个结点u0，使deg(u0)=1，若不然，即所有结点u有deg(u) 2则2e 2v，即ev，与假设e=v-1矛盾。,删去u0及其关联的边，而得到新图T，由归纳假设可知T无回路，在T中加入u0及其关联边又得到T，故T是无回路的，若在连通图T中增加新的边(ui,uj) ，则该边与T中ui到uj 的的一条路构成一个回路，则该回路必是唯一的，否则若删去此新边，T中必有回路，得出矛盾。,证明（4）（5） 若图 T不连通，则存在结点ui与uj, 在ui与uj之间没有路, 显然若加边ui,uj不会产生回路，与假设矛盾。又由于T无回路，故删去任一边，图就不连通。,证明（5）（6） 由连通性可知，任两结点间有一条路，若存在两点，在它们之间有多于一条的路，则T中必有回路，删去该回路上任一条边，图仍是连通的，与（5）矛盾。,证明（6）（1） 任意两结点间有唯一条路，则图T必连通，若有回路则回路上任两点间有两条路，与（6）矛盾。,定理2 任一棵树中至少有两片树叶。,证明 设树T=，|V|=v, 因为T是连通图，对于任意viT，有deg(vi)1且deg(vi)=(|V|1)=2v2若T中每个结点度数大于等于2，则deg(vi)2v，得出矛盾。若T中只有一个结点度数为1, 其它结点度数大于等于2，则 deg(vi)2(v1)+1= 2v1得出矛盾。故T中至少有两个结点度数为1。,定义2 若图G的生成子图是一棵树，则该树称为G的生成树。,树枝 设图G有一棵生成树T，则T中的边称作树枝。,弦 图G的不在生成树中的边称作弦。,补 所有弦的集合称作生成树T的补。,定理3 连通图至少有一棵生成树。,1,7,5,6,4,3,2,e,d,c,b,a,秩 假定G是一个有n结点和m条边的连通图，则T的生成树正好有n-1条边。因此要确定G的一棵生成树，必须删去G的m-(n-1)=m-n+1条边。数m-n+1称为连通图的秩。,定理4 一条回路和任何一棵生成树的补至少有一条公共边。,定理5 一个边割集和任何生成树至少有一条公共边。,带权的生成树。,设图G中结点表示一些城市，各边表示城市间道路的连接情况。边的权表示道路的长度（长度、运输量、费用等）。,如果我们要用通讯线路把这些城市联系起来，要求沿道路架设线路时，所用的线路最短，这就是要求一棵生成树，使该生成树是图G的所有生成树中边权和为最小。,定义3 在图G的所有生成树中，树权最小的那棵生成树，称作最小生成树。,定理可何加心的设图o有n个结点，以下算法产生 的是最小生成树。 a）选取最小权边，生边数6一4l N6一。一工结束，否则转心 中设已选择边为内，向，在o中选取不同于el，q， ， e。的边 e；。，使 el， e， eo elJ中无回路且 el。是满足此 条件的最小边。 06各一十1，转O。 证明设见为由上述算法构造的一个国，它的结点是图o 的个结点，的边是电，内，民一1。根据构造，队没有回路， 由定理 7cy·1可知 To是一棵树，且为国o的失成树。 下面证明九是最小生成树。 设G的最小生成树是T若T与TO相同，则To是o的t 小生成树。若p与饥不同，则在中至少有一条边一十：，使得 向十1不是p的边，但必，O，e；是p的边。因为Y是树我们在 少中加上边8；1，必有一条国路，而队是树，所以矿中必存在 某条边不在To中。对于树T，若以边ef。宜换人则得到新的 一棵树 T，但树 T的权 O（w一OoO的一O（j）因为 p 是最小生成树，故O（T）（T）即 D（l）o0或o（。）PO 因为0，N，1是y的边。且在仇e，。e；，o1中没有回 路，故o构0不可能成立，因为否则在见中，自1，内， ，e之后将取而不能取ell，与题设矛盾。于是OwoO（j）， 因此 T也是 o的一棵最小生成材，但是 T与 TO的分共边比 T TO的公共边数多1，用 T，t换T， t复上面论证直至得到与 风有卜1条公共边的最小生成材，这时我们断定马是最小生成 D 例如国百万sop出一个赋权连通图，粗线表示接上述算法 得到的最小生成树。 以上算法中假设q中边权全不相同，实际上，这种算法完全 适用于任意过权的情况，若有两条边权数相同，我们可以让其中的 一条的权改变一个很小的量，因为o中边数有限，总可选择这个 改变量而不影响最小生成树的最小性。,yi ledm 二 WAfxt 图 773 ffi 7N4 例如M774出一个赋权连N To， o（s，心一1， O（mp，。a）一2， O （，wi）一2， O（eq，。）一3， O仰，。）一2。 O（。，。）一1，O（N，心一3，o（。，。）一2，最小生成材有边 （n，），恤，。），（，叫，（q，叫，以粗线表示。 TO的权 D（TO 6。 78回一 （1）当且仅当连通国的每条边均为创边时，该连通图才是一棵树。 （2）一棵树有两个结点度数为 2，一个结点度数为 3， at结点度数为 、问它有几个度数为 1的结点。 （3）一棵树有。个结点度数为2，N个结点度数为a，N个结点度数 为 k， rq它有几个度数为1的结点。 （4）设马和n是在遭围o的两棵生成协。是在 Ti申但不在Ts中 的一条机证明存在边久它在马中仅不在马中，使得（马一扣Du他和 （马一他UN都是o的生成批 （5）设G一（K用为连通N，且eEE。证明：当且仅当。是G的割边 时，o才在GW每棵生成材中。 O）对于用工1民利用Kr刚出d具法求一棵景小生成树,
