离散数学期末复习试题及答案(五)(3)

离散数学期末复习试题及答案

n1+n2＝n,由ni≥1,ni≤n - 1 (i =1,2)

m ≤n1(n1-1)/2 + n2(n2-1)/2 ≤(n-1)(n1+n2-2)/2 = (n-1)(n-2)/2 与条件矛盾.

证三:若G不连通,__

__

G连通(由第四题结论), G是(n,m')图

m'≤(n(n-1)/2)-m≤(n(n-2))/2-((n-1)(n-2)/2) =(n-1) 由定理3,__G不连通,矛盾.

证四：若 G不连通，至少有 2 点 a ,b不连通, 其余(n-2)个点不会同时 与 a ,b 有边连通,则 m ≤(n(n-1)/2)-1-(n-2)=(n-1)(n-2)/2 矛盾.

6．写出下图的邻接矩阵，可达性矩阵，并求它的强分图。? V1

2 V3

5 V4

01000 1011 0

0010 0 10000 01011 01011 6. A= 1

0000 P= 1011 p pT= 00001 1

00100

01011 01011 0

1

0 0

1

1

1

0

1

1

1

7．确定下图中ａ到ｚ的最短路径?

b 10 f

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库离散数学期末复习试题及答案(五)(3)在线全文阅读。