(5)→(6) 如果G是连通的且G中任何边均为桥,则G中没有回路,但在任 何两个不同的顶点之间加一条新边,在所得图中得到唯一的 个含新边的圈。 因为G中每条边均为桥,删掉任何边,将使G变成不连通图, 所以,G中没有回路,也即G中无圈。 又由于G连通,所以G为树,由(1)→(2)可知, u,v∈V,且wν,则u与ν之间存在唯一的路径r, 则rU(u,v)((,)为加的新边)为G中的圈, 显然圈是唯一的
如果G是连通的且G中任何边均为桥，则G中没有回路，但在任 何两个不同的顶点之间加一条新边，在所得图中得到唯一的 一个含新边的圈。 因为G中每条边均为桥，删掉任何边，将使G变成不连通图， 所以，G中没有回路，也即G中无圈。 又由于G连通，所以G为树，由(1) (2)可知， u,v∈V，且u≠v，则u与v之间存在唯一的路径Г， 则Г∪(u,v)（(u,v)为加的新边）为G中的圈， 显然圈是唯一的。 (5)(6)
6)→(1) 如果G中没有回路,但在任何两个不同的顶点之间加一条新边, 在所得图中得到唯一的一个含新边的圈,则G是树。 只需证明G是连通的。 Vu,v∈V,且u+v,则新边(,)∪G产生唯一的圈C, 显然有C-(u,)为G中u到v的通路,故u~v, 由u,y的任意性可知,G是连通的
如果G中没有回路，但在任何两个不同的顶点之间加一条新边， 在所得图中得到唯一的一个含新边的圈，则G是树。 只需证明G是连通的。 u,v∈V，且u≠v，则新边(u,v)∪G产生唯一的圈C， 显然有C -(u,v)为G中u到v的通路，故u～v， 由u,v的任意性可知，G是连通的。 (6)(1)
无向树的性质 定理16.2设T是n阶非平凡的无向树,则?中至少有两片树叶。 证明 设T有x片树叶,由握手定理及定理16.1可知, 2(n-1)=()≥x+2(n-x) 由上式解出x≥2
定理16.2 设T是n阶非平凡的无向树，则T中至少有两片树叶。 证明 设T有x片树叶，由握手定理及定理16.1可知， 2( 1) ( ) 2( ) i n d v x n x − = + − 由上式解出x≥2。 无向树的性质
例16,1 例16.1画出6阶所有非同构的无向树。 解答设T是6阶无向树。 由定理16.1可知,T的边数m2=5, 由握手定理可知,Σdn(vy)=10,且6(7)≥1,△(T)≤5。 于是T的度数列必为以下情况之一。 1)1,1,1,1,1,5 (4)对应两棵非同构的树, 在一棵树中两个2度顶点相邻, (3)1,1 3,3 在另一棵树中不相邻, (4)1,1,1,2,2,3 其他情况均能画出一棵非同构 (5)1,1,2,2,2,2 的树
例16.1 例16.1 画出6阶所有非同构的无向树。 解答 设Ti是6阶无向树。 由定理16.1可知，Ti的边数mi＝5， 由握手定理可知，∑dTi(vj)＝10，且δ(Ti)≥1，△(Ti)≤5。 于是Ti的度数列必为以下情况之一。 (1) 1，1，1，1，1，5 (2) 1，1，1，1，2，4 (3) 1，1，1，1，3，3 (4) 1，1，1，2，2，3 (5) 1，1，2，2，2，2 (4)对应两棵非同构的树， 在一棵树中两个2度顶点相邻， 在另一棵树中不相邻， 其他情况均能画出一棵非同构 的树
例16,1 T 口人们常称只有一个分支点,且分支点的度数为m1的 n(n≥3)阶无向树为星形图,称唯一的分支点为星心
例16.1 ❑ 人们常称只有一个分支点，且分支点的度数为n-1的 n(n≥3)阶无向树为星形图，称唯一的分支点为星心