试题详情
简答题证明：生成树中最长路径的起点和终点的度均为1。
  • 用反证法证明。
    设v1，v2，…，vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然v1，v2，…，vk，v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。
    同理可证起点v1的度不能大于1，只能为1。

  • 关注下方微信公众号，在线模考后查看

热门试题