答案(电子科大版)图论及其应用第2章.doc

《答案(电子科大版)图论及其应用第2章.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题二：l证明：非平凡树的最长路的起点和终点均是1度的。证明设是非平凡树T中一条最长路，若则与在中的邻接点只能有一个，否则，若与除了中顶点之外的其他顶点相连，则可以继续延长，这与是最长路是相矛盾的。若与上的某顶点相连，则就构成了圈，这与数相矛盾，推出不是最长路。即说明与是树叶，则与均是一度的。所以非平凡树的最长路的起点和终点均是度的。9.证明：顶点度数为偶数的连通图本身可构成一个包含所有边的闭迹。证明：证明：由于是连通非平凡的且每个顶点度数为偶数，所以中至少存在圈,从中去掉中的边，得到的生成子图,若没有边，则的边集合能划分为圈。

2、否则，的每个度数均为偶数的连通图，反复这样抽取，最终划分为若干圈。设是的边划分中的一个圈。若仅由此圈组成，则显然是闭迹。否则，由于连通，所以，必然存有公共顶点。于是，是一条含有与的边的迹，如此拼接下去，得到包含的所有边的一条闭迹.l16.Kruskal算法能否用来求：（1）赋权连通图中的最大权的树？（2）赋权图中的最小权的最大森林？如果可以，怎样实现？答：1、不能，由Kruskal算法得到的任何生成树一定是最小生成树。2、能