解：
S l(v2) l(v3) l(v4) l(v5) l(v6) t l(t) {v1} 3 4 ? ? ? v2 3 {v1,v2} 4 13 ? ? v3 4 {v1, v2, v3} 7 6 ? v5 6 {v1,v2, v3, v5} 7 10 v4 7 {v1,v2, v3, v5, v4} 9 v6 9 {v1,v2, v3, v5, v4, v6}
故v1到v2, v3, v4, v5, v6的距离分别是3，4，7，6，9。 109、求下图的可达矩阵。
d a
e
b
c 解：
该图的邻接矩阵为
?1??1A=?0?0???0则
1000??0100?1000? 0001??0010??2?1??1A=?0?0??0?2
10100000??100?000?001??010??
?2??1=?1?0???01100??2000?0100? 0010??0001???3??3A=?1?0???033100??1200?2000? 0001??0010?? 45
?6??4A=?3?0???044300??5100?1200? 0010??0001??
故图的可达矩阵为
?1??1P =?1?0???01100??1100?1100? 0011??0011??110、求下列图的生成树。
解：
下面是它的两棵生成树：
111、在一个有n个顶点的G=
设v0e1v1e2?el vl是从u=v0到v=vl的长为l的通路。 若l?n-1，则结论显然成立。
否则因为l+1>n，故v0，v1，?，vl中必有一个顶点是重复出现的。不妨设vi=vj(0?i 若新通路的长度?n-1，则结论得证。否则对新通路重复上述过程，必可以得到一条从u到v的长为n-1的通路。 112、设简单平面图G中顶点数n=7，边数m=15。证明：G是连通的。 证明： 设G具有k个连通分支G1，G2，?，Gk。设Gi的顶点数为ni，边数为mi，i=1,2,?,k。 先证每个连通分支的顶点数都大于1。否则说明G中有孤立结点。由于G是简单图，从而要使G的边数是15，则G只有两个连通分支，其中一个是由孤立结点导出的，另一个是K6。但K6不是平面图，故要每个连通 46 分支的顶点数都大于1。 同理可证，每个连通分支的顶点数都大于2。 由此可得，G的每个连通分支至少有3 个顶点。从而 mi?3ni-6 即m= ?mi?1ki??(3ni?6)=3n-6k i?1k从而15?21-6k，即k?1。从而k=1，故G是连通图。 113、已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？ 解： 设它有k个1度顶点，则由欧拉握手定理 ?v?Vdeg(v)=2|E| 可得 2|E|=k+4+3+12=k+19。再由于它是一棵树，故 |E|=k+2+1+3-1=k+5 从而2(k+5)=k+19, k=9。故它有9个1度顶点。 114、有向图G是强连通的?G中有一回路，它至少通过每个顶点一次。 证明： ?设G= P1。故从P1和P2首尾相接可得到一条经过u和v的回路C1。 若C1经过G中所有顶点至少一次，则C1就是满足结论要求的回路。否则若C1没有经过顶点w，则类似地我们可得到一条经过u和w的回路C2。从C1和C2我们可得到一条经过更多顶点的回路C3（先从u经过P1到v,再从v经过C2回到v,再从v经过P2回到u）。 对C3重复上述过程，直到得到一条经过所有顶点的回路为止。 ?若G中存在一条经过G中所有顶点至少一次的回路，则G中任意两个顶点是相互可达的，从而G是强连 通的。 115、一个有向图是单向连通图? 它有一条经过所有结点的路。 证明： ?设G= 径P1。 若P1经过G中所有顶点至少一次，则P1就是满足结论要求的路径。否则若P1没有经过顶点w，则如果v经过路径T可达w, 连接P1和T我们可得一条经过P1经过的所有顶点及w的更长的路径P2；否则若w经过路径S可达u，连接S和P1我们也可得一条经过w及P1经过的所有顶点的更长的路径P2；再否则我们一定可以找到P1经过的两个相邻顶点t和s，t到s有边，t经过路径T1 可达w，w经过路径T2可达s（否则就与u可达w，w可达v矛盾），我们构造这样一条路径P2：从u出发经过P1到达t,t经过路径T1到达w，再从w 47 出发经过路径T2到达s，然后从s出发经过P1到达v。这是一条经过w及P1所经过的所有顶点的更长的路径。 u? ?v u? ?v T S w? ?w P u ? ?t ?s ?v T1 T2 ?w 对P2重复上述过程，直到得到一条经过所有顶点的路径为止。 P1 P1 ?若G中存在一条经过G中所有顶点至少一次的路径，则G中任意两个顶点中至少有一个可达另一个， 从而G是单向连通的。 寄语： 希望大家能在考试中取到好的成绩，谢谢！ 48