证明：生成树中最长路径的起点和终点的度均为1。
正确答案:用反证法证明。
设v1，v2，…，vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然v1，v2，…，vk，v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。
同理可证起点v1的度不能大于1，只能为1。
设v1，v2，…，vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然v1，v2，…，vk，v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。
同理可证起点v1的度不能大于1，只能为1。
答案解析:有
微信扫一扫手机做题