例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阶无向树