《离散数学》题库及答案 下载本文

解:

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

若新通路的长度?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=是强连通图。任取u,v?V,则u和v相互可达,即从u到v有路径P1,从v到u有路径

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=是单向连通图。任取u,v?V,则u可达v或v可达u。不妨设u可达v,即从u到v有路

径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