可求得其强分图矩阵为: 因此, 此图有两个强分图, 一个包含一个结点V9 , 一个包含其它的8个节点。由于两个强分图之间存在有向道路,因此全部9个结点,构成了单向分图■ 28. 证明:一个连同无向简单图中,任意两条最长路至少有一个公共顶点。 10 证明:假设两条最长路p1=v1v2 .. .vk,p2=u1u2 .. .uk没有公共点,那么两条道路上的点集之间就有道路相连, 否则就不是连通图了。设此道路起点是p1上m点, 终点是p2上的w点.可根据如下情况进行调论: (1)m,w是p1,p2的中间结点, 那么可构成新道路 P=v1v2 ...m...w... uk , 此路至少比P1长 1, 矛盾。(2) 假设 m和w 不能均分 p1,p2, 那么可以将两个长路段和 m,w 之间的道路进行拼接,那么可得到比 p1 长的道路,与p1,p2是最长路矛盾。因此任意两条最长路至少有一个公共顶点■ 29. 证明:若G是n 阶无向简单图,G 中每一对不相邻的顶点的度数之和至少是 n -1,则G 是连通图。证明:假设 G 不是连通图, G1, G2是G 的两个连通分支,分别为 n1,n2 阶连通无向简单子图,则 n1+n2 ≤n。对 G1 中任意结点 v1, 和 G2 中任意结点 v2 而言, v1 的最大点度为 n1-1,v 2 的最大结点度为 n2-1; 则 v1,v2 的点度之和,最大为 n1+n2-2 ≤ n-2 < n-1. 与题设条件矛盾。矛盾的导出,是因为假设 G 不是连通图引起的,因此,原题设结论成立■ 30. 求出图 10. 34 的邻接矩阵、可达性矩阵、强分图和关联矩阵。图 10. 34 解:对图的结点和边进行编号如下: e12 e11 e10 e9 e8 e7 e6 e5 e3 e2 e1 e4 v7 v1 v3 v6 v5 v4 v2 邻接矩阵: 因此可达矩阵为:
全文预览
