9.1无向树及生成树.ppt

。用T表示,T中度数为1的点称为叶,度数大于1的结点称为分支点或内点。非连通图的每个连通分支是树的无向图称为森林。平凡图也是树称为平凡树。:树图中v3,v5是分支点,其他点均是叶子。=<V,E>,以下关于树的命题是等价的。<1>T是连通且无回路;<2>T无回路,且m=n-1,其中|V|=n,|E|=m;<3>T连通,且m=n-1;<4>T无回路,但增加一边后得到且仅得一个回路;<5>T连通,但删去任一边后就不连通;<6>>每一对结点间有且仅有一条通路。:任何非平凡树,T=<V,E>至少存在两个叶。证明:因T连通则u∈T,deg(v)≥1。设T有k个一度点,其它点均大于等于2,则2m=∑deg(vi)≥k+2(n-k)=2n-k因m=n-1,∴2(n-1)≥2n-k,则k≥2。=<V,E>是树,如|V|=20,树叶共有8个,其它点的度数均≤3,问题:2度点和3度点各有多少。解:设2度点为x个,则3度点为20-8-X。因2m=∑deg(vi)而m=n-1∴2×(20-1)=1×8+2x+3(20-8-x)解为x=6,则3度点共有20-8-6=,则称这棵树为G的生成树,设G的一棵生成树为T,则T中的边称为树枝,在G中而不在T中的边称弦,所有弦的集合称为生成树T的补。:。证明:如果G无回路,则G本身就是它的生成树;如G有回路,则在回路上任取去掉一条边仍是连通的,如G仍有回路,则继续在该回路上去掉一条边,直到图中无回路为止,此时该图就是G的一棵生成树。一般如果G有n个点m条边连通,则m≥n-1,则G删除m-(n-1)条边。破坏了m-(n-1)个回路,必成G的一棵生成树,这是”破圈法”。也可以从m条边中选取n-1条边并使它不含有回路,这是”避圈法”。,则(1)G的任何边割集与T至少有一条公共边(2)G的任何回路与T的补至少有一条公共边。因边割集的边均去掉,图就不连通,则边割集至少有一条边要留在树T中,而回路中至少要去掉一边,因而该边就在T的补中。