例16,2 例16.27阶无向图有3片树叶和1个3度顶点,其余3个顶点的度 数均无1和3。试画出满足要求的所有非同构的无向树。 解答设T为满足要求的无向树,则边数m=6,于是 ∑d()=12=e+3+d(v4)+d(vy)+d(vb) 由于(y)1∧d()≠3,而且(y)≥1且d(y)≤6,j=45,6, 可知d(y)=2,产=45,6。于是T的度数列为 由度数列可知,T中有一个3度顶点v;v的邻域N(v)中有3个顶 点,这3个顶点的度数列只能为以下三种情况之 1,1,2 设它们对应的树分别为T1,T2,T3。此度数列只能产生这三棵 非同构的7阶无向树
例16.2 例16.2 7阶无向图有3片树叶和1个3度顶点，其余3个顶点的度 数均无1和3。试画出满足要求的所有非同构的无向树。 解答 设Ti为满足要求的无向树，则边数mi＝6，于是 ∑d(vj)＝12＝e+3+d(v4 )+d(v5 )+d(v6 )。 由于d(vj)≠1∧d(vj)≠3，而且d(vj)≥1且d(vj)≤6，j＝4,5,6， 可知d(vj)＝2，j＝4,5,6。于是Ti 的度数列为 1，1，1，2，2，2，3 由度数列可知，Ti中有一个3度顶点vi，vi的邻域N(vi)中有3个顶 点，这3个顶点的度数列只能为以下三种情况之一： 1,1,2 1,2,2 2,2,2 设它们对应的树分别为T1，T2，T3。此度数列只能产生这三棵 非同构的7阶无向树
例16,2
例16.2
°例题 例题已知无向树中,有1个3度顶点,2个2度顶点,其余 顶点全是树叶,试求树叶数,并画出满足要求的非同构 的无向树。 解答设有x片树叶,于是结点总数为 n=1+2+x=3+x 由握手定理和树的性质m=n-1可知, 2m=2(n-1)=2×(2+x) =1×3+2×2+x 解出x=3,故有3片树叶。 故T的度数应为1、1、1、2、2、3。T1
例题 例题 已知无向树T中，有1个3度顶点，2个2度顶点，其余 顶点全是树叶，试求树叶数，并画出满足要求的非同构 的无向树。 解答 设有x片树叶，于是结点总数为 n＝1+2+x＝3+x 由握手定理和树的性质m＝n−1可知， 2m＝2(n−1)＝2×(2+x) ＝1×3+2×2+x 解出x＝3，故T有3片树叶。 故T的度数应为1、1、1、2、2、3
°例题 例题已知无向树T有5片树叶,2度与3度顶点各1个,其余顶 点的度数均为4,求T的阶数n,并画出满足要求的所有非同 构的无向树。 解答设T的阶数为n,则边数为n-1,4度顶点的个数为n-7。 由握手定理得 2m=2(-1)=5×1+2×1+3×1+4(-7) 解出n=8,所以4度顶点为1个。 故T的度数列为1、1、1、1、1、2、3、4
例题 已知无向树T有5片树叶，2度与3度顶点各1个，其余顶 点的度数均为4，求T的阶数n，并画出满足要求的所有非同 构的无向树。 解答 设T的阶数为n, 则边数为n−1，4度顶点的个数为n−7。 由握手定理得 2m = 2(n−1) = 51+21+31+4(n−7) 解出n = 8，所以4度顶点为1个。 故T的度数列为1、1、1、1、1、2、3、4。 例题
°例题 T2 节結束
小节结束 例题