第9章树 ⑥由(5)可得树的定义 每对顶点之间有唯一一条初级通路,那么T必连通, 若有回路,则回路上任意两个顶点之间有两条初级通 路,与(5)矛盾。故图连通且无回路,是树
第9章 树 ⑥由（5）可得树的定义。 每对顶点之间有唯一一条初级通路，那么T必连通， 若有回路，则回路上任意两个顶点之间有两条初级通 路，与（5）矛盾。故图连通且无回路，是树
第9章树 定理91.2任何一棵非平凡树T至少有两片树叶。 证明设T是(n,m)图,n2,有k片树叶,其余 顶点度数均大于或等于2。则 ∑d(u)≥2(n-k)+k=2n 而 ∑d(u)=2m=2(n-k)=2n 所以2n-2>2n-k,即心2
第9章 树 定理9.1.2 任何一棵非平凡树T至少有两片树叶。 证明 设T是（n，m）图，n≥2，有k片树叶，其余 顶点度数均大于或等于2。则 1 1 ( ) 2( ) 2 ( ) 2 2( ) 2 2 n i i n i i d n k k n k d m n k n = = − + = − = = − = − 而 所以2n-2≥2n-k，即k≥2
第9章树 【例912】T是一棵树,有两个顶点度数为2,一个 顶点度数为3,三个顶点度数为4,T有几片树叶? 解设树T有x片树叶,则T的顶点数 n=2+1+3+x T的边数 2=-1=5+x 又由握手定理
第9章 树 【例9.1.2】 T是一棵树,有两个顶点度数为2，一个 顶点度数为3，三个顶点度数为4，T有几片树叶？ 解 设树T有x片树叶，则T的顶点数 n=2+1+3+x T的边数 m=n-1=5+x 又由握手定理 1 2 ( ) n i i m d = =
第9章树 得 2·(5+x)=2·2+31+43+x 所以x=9,即树7有9片树叶 请读者自己画出两棵具有上述度数列的非同构的树
第9章 树 得 2 · （5+x）=2·2+3·1+4·3+x 所以x=9，即树T有9片树叶。 请读者自己画出两棵具有上述度数列的非同构的树
第9章树 【例913】画出所有非同构的七阶无向树。 解设T是七阶无向树。因为n-7,所以m=6,又因 为2m=∑d(u 所以七个顶点分配12度,且 由树是连通简单图知1≤d(v)≤6。则的度数列必是 下列情况之一
第9章 树 【例9.1.3】 画出所有非同构的七阶无向树。 解 设Ti是七阶无向树。因为n=7，所以m=6，又因 为 , 所以七个顶点分配12度，且 由树是连通简单图知1≤d（v）≤6。则Ti的度数列必是 下列情况之一。 1 2 ( ) n i i m d = =