发布时间 : 星期一 文章四川大学离散数学（冯伟森版）课后习题答案习题参考解答（图论部分）更新完毕开始阅读
去找 http://www.7zhao.net 当ｋ为偶数时，道路可扩充为v1…vk/2…u…vk/2+1…vk,而当ｋ为奇数时，不管ｖｋ＋１／２与ｕ之间是如何单向可达的，都可以构造出更长的有向道路，矛盾，所以Ｇ中一定存在包含所有结点的有向道路■
26. 无向图G如图10.32所示，先将此图顶点和边标出，然后求图中的全部割点和割边。
图10.32 解：标注如下所示： ｕ３ ｕ５ ｕ７ ｕ１ ｕ４ ｕ２ ｕ６ ｕ８ ｕ９ 根据标记后的图，可求得割点分别为：ｕ４，ｕ７，ｕ８，割边分别为：ｕ４ｕ５，ｕ７ｕ８，ｕ８ｕ９■ 27. 求图10.33的全部强分图和单向分图。 图10.33
解：将图重新标记如下：
9
去找 http://www.7zhao.net ｖ１ ｖ４ ｖ２ ｖ５ ｖ９ ｖ６ ｖ３ ｖ７ 那么此图的邻接矩阵为，通过计算可求得其强分图矩阵为： 因此，此图有两个强分图，一个包含一个结点Ｖ９ ，一个包含其它的８个节点。由于两个强分图之间存在有向道路，因此全部９个结点，构成了单向分图■ 28. 证明：一个连同无向简单图中，任意两条最长路至少有一个公共顶点。 证明：假设两条最长路ｐ１＝ｖ１ｖ２．．．ｖｋ，ｐ２＝ｕ１ｕ２．．．ｕｋ没有公共点，那么两条道路上的点集之间就有道路相连，否则就不是连通图了。设此道路起点是ｐ１上ｍ点，终点是ｐ２上的ｗ点．可根据如下情况进行调论：（１）ｍ，ｗ是ｐ１，ｐ２的中间结点，那么可构成新道路 Ｐ＝ｖ１ｖ２．．．ｍ．．．ｗ．．．ｕｋ，此路至少比Ｐ１长1，矛盾。（2）假设m和w不能均分p1,p2,那么可以将两个长路段和m,w之间的道路进行拼接，那么可得到比p1长的道路，与ｐ１，ｐ２是最长路矛盾。因此任意两条最长路至少有一个公共顶点■ 29. 证明：若G是n阶无向简单图，G中每一对不相邻的顶点的度数之和至少是n-1，则G是连通图。 证明：假设G不是连通图，G1，G2 是G的两个连通分支，分别为n1,n2阶连通无向简单子图，则n1+n2≤n。对G1中任意结点v1,和G2中任意结点v2而言，v1的最大点度为n1-1,v2的最大结点度为n2-1;则v1,v2的点度之和，最大为n1+n2-2≤n-2 图10.34 10 去找 http://www.7zhao.net 解：对图的结点和边进行编号如下： ｖ１ ｅ２ ｖ３ ｅ７ ｅ５ ｖ５ ｅ１１ ｅ６ ｅ８ ｅ１０ ｅ９ ｖ６ ｅ１ ｅ３ ｅ１２ ｖ２ ｅ４ ｖ４ ｖ７ 邻接矩阵： 因此可达矩阵为： 强分图矩阵为： 关联矩阵为： ■ T31. 设P= (pij) n×n是可达性矩阵。证明:P错误！未找到引用源。P中第i行中非零元素所在列号给出了包含结点vi的强分图的全部结点编号。 证明：根据强分矩阵的计算过程可知，其包含的含义是结点间双向可达信息。根据有向图的双向可达关系是一个等价关系，因此P错误！未找到引用源。PT中第i行中非零元素所在列号既是一个等价类，所以包含了一个强分图的所有结点■ 已完成[1，2，3，4，5，6，7，8，9，10，11，12，13,14，15，16，17，18，19，２０,21，２３，２４，２５，２６，２７，２８，29，３０，31] 第２２题未证明 11 去找 http://www.7zhao.net 习题十一 1. 设一个树中度为k的结点数是nk（2≤k），求它的叶的数目。 解：设T的节点总数为n，叶节点数目为t ，根据题意及握手定理有： t + n2 + n3 + …+ nk = n (1) t + 2n2 + 3n3 + …k(nk) = 2(n-1) (2) 握手定理 (1),(2)联立求解得： t = n3 + 2n4 + … (k-2)nk + 2■ 2. 证明：树T中最长道路的起点和终点必都是T的叶。 证明：假设T中最长道路P=vi1vi2…vik的起点或终点不是T的叶结点，设d(vi1)>1,则vi1的 12l 所有邻接点(v‘,v’…,v’)都在P中，那么在T中可以找到一个回路,那么截取道路P, 得到 l 回路C= vi1 …v’ vi1 .与T中无回路矛盾。对于d(vik)>1时同理。因此，假设不成立，即最长道路P的起点和终点都是T的叶节点■ 3. n（n≥3）阶无向树T的最大度Δ至少为几？最多为几？ 解：当T中只有一个枝点时，Δ = n-1,为最大值。 当T构成一条链时，只有两个叶结点，其余结点都为2度点，此时Δ = 2，为最小值，因此Δ至少为2 ，最大为n-1■ 4. n（n≥3）阶无向树T的最大度Δ=2，则T中最长的简单道路为几？ 解：根据第3题结论，当无向树T的最大度Δ=2时 ，T构成一条链，以此最长的简单道路包含所有的节点，道路长度L=n-1■ 5. 证明：任何无向树都是二部图。 证明：以树Ｔ中任意结点ｕ为起点，将与ｕ最短距离为偶数的结点放入ｖ１结点集合，将与ｕ最短距离为奇数的结点放入ｖ２结点集合，那么这两个结点集合中，显然不存在公共点，同时两个结点集合组成了树的全部结点，因此是数Ｔ的结点集合的一个分化。假设在Ｖｉ集合中存在两个结点ｕ１，ｕ２是邻结点，那么就存在如下道路：ｐ＝ｕ．．．ｕ１ｕ２．．．．ｕ， 12