离散数学期末复习试题及答案
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