2023年第十二章习题答案

第十二章习第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作为序，利用将有序树转化为位置二元树的算法，求得其对应的位置二元树如右图所示。4u3u5u7u0u1u2u6u8u9u1014.对于图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,,,SSSS12357