《离散数学》题库及答案

解：

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=中，u,v?V。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的通路。 证明：

设v0e1v1e2?el vl是从u=v0到v=vl的长为l的通路。 若l?n-1，则结论显然成立。

否则因为l+1>n，故v0，v1，?，vl中必有一个顶点是重复出现的。不妨设vi=vj(0?i