离散数学-第十二章习题答案 VIP专享VIP免费

第12章习题答案1.设T是一个非平凡树，证明T中最长基本链的起点和终点的次数为1。证明：假设P是T中最长的基本链，P的起点或终点的次数不为1，即它的次数至少是2，则至少有一个顶点，令其为u，与P的起点或终点邻接。若u在P上，则构成圈，与T是树矛盾，若u不在P上，则存在比P更长的基本链，这与P是T中最长的基本链矛盾。因此，非平凡树T中最长基本链的起点和终点的次数必为1。2.证明恰好有两个顶点的次数为1的树必为一基本链。证明：假设T是任意一个恰好有两个顶点的次数为1的树，如果T不是一基本链，则至少有一个分支顶点的次数大于2。设T有n个顶点，则T有n-2个分支顶点，n-1条边。根据定理9.1，T的顶点的次数之和等于T的边数的2倍，可知2（n-1）2+2（n-2）因此得到2n-22n-2，矛盾。故T必为一基本链。即恰好有两个顶点的次数为1的树必为一基本链。3.一个树有n2个顶点次敉为2，n3个顶点次数为3，…，nk个顶点次数为k，问这个树有几片树叶？解：设这个树为T，有x片树叶，则T有x+n2+n3+…+nk-1条边。根据定理9.1，T的顶点的次数之和等于T的边数的2倍，有x+2n2+3n3+…+knk=2（x+n2+n3+…+nk-1）解得x=n3+2n4+3n5+…+（k-2）nk+2即这个树有n3+2n4+3n5+…+（k-2）nk+2片树叶。7.证明在完全二元树中，弧的总数等于2(nt-1)，这里nt是树叶的数目。证明：设完全二元树T有n个顶点，m条弧。因为它有nt片树叶，所以除树叶以外的顶点有n-nt个。由于在完全二元树中，除树叶以外的顶点的引出次数均为2，每片树叶的引出次数均为0，故所有顶点的引出次数之和为2（n-nt），它等于弧的总数m。又因为1nm，故有2（n-nt）=1n，解得n=2nt-1。因此m=n-1=2(nt-1)。11.图12.11给出了一个有序树，试求其对应的位置二元树。解：把该树顶点标记iu的下标i作为序，利用将有序树转化为位置二元树的算法，求得其对应的位置二元树如右图所示。4u3u5u7u0u1u2u6u8u9u10u14.对于图12.13的带权图，用Kruska算法求出它的最小生成树。解：最小生成树T如右图所示。15.图12.14给出了一个连通无向图G，试求G的任意一个生成树，并找出关于该生成树的基本圈组和基本割集组。解：求得G的生成树T如右图所示。基本圈有C1=(e1,e5,e6),C2=(e2,e6,e7)，C3=(e3,e7,e8),C4=(e4,e5,e8)T的基本圈组为1234,,,CCCC。基本割集有1514,,Seee，2612,,Seee，3723,,Seee，4834,,Seee；T的基本割集组为1234,,,SSSS123577e6e5exvwyu8e