10. 设G为n阶简单无向图，对G的任意结点v, dG(v)?(n?1)/2，证明G是联通的。 证明：
ViVj
任取Vi,Vj, 因为dG(v)?(n?1)/2, 故至少存在??多还剩余n?2???n?1?个点与Vi相连，最??2?n?1??n?1?n?1??1?（除去Vi,Vj剩余的点）。故对于Vj???222????至少存在一个与Vi连接的点与Vj相连，因此Vi与Vj联通。由Vi与Vj选取的任意性，G联通。
11. 证明：对于小于或等于n的任意正整数k, n阶连通无向图有k阶连通子图。
证明：n阶连通无向图，则n个顶点中的任意点与其他顶点均可达。取其中的k个顶点也满足该性质，故存在k阶连通子图。
7.4第181页
1.
解：根据图7-26得邻接矩阵为：
v1到v4：
长度为1的基本路径为：v1?v4 长度为2的基本路径为：v1?v2?v4 长度为4的基本路径为：v1?v2?v3?v2?v4
??0101???111???212???32A??0011?00201?00122?0041??0101??，A2???0111??,A3???0212??,A4???032?0100????0011????0202????0122.
解：（1）对于n=1,2,…,6，试计算矩阵An1中的各元素。
??001110??1211??557?000011??310111??4222225A1?100100???122120???3?522521???101010?，A2?10??1???211311?，
A?1???52547?110101??112141??7274?010010????110112???5?23225??179916139???984997??382233395122?A4?94109144???221618223317?1???169917139?，A5?331818332618????1???392233385122??1391413249????974998???513326514433??221718223316????123737712212173??735044737749?A6?7744667710244??1???122737712312173?
???1217710212116877??734944737750??（2）
3?3?3?? 2??2?3?2??2?，
?5?2??，?0?0??0?1A2??1?1??0?0??2?0??1?3A2??4?3??0?0??12?0??6?5A2??17?13??0?0?001100??201?020000011????101001000???2??100010100?，A2?101001000???100000??000?000100000???1100?0000??0100??3100? 1200??0011?0011??014300??7046600??0400000?000022?????4032400?003100????4??60211600? 032400?，A2?6046700?014200????200000?0000022???0000022?200000????00000446171300??300?0800044????170211600???6??31011141700?，A2?2906171200???00000??00?0000000???17312900?00000??11141700??14453100? 17313000??00044?00044??（3）试求出图中G1和G2中的所有基本循环。
k对于A1和A2，aii表示结点vi(i?1,2,...7)上长度为k的循环的个数。
3. 对于图7-26中的有向图，试求出邻接矩阵A的转置AT,AAT,ATA,列出矩阵A?AT的元素值，并说明它们的意义。
解：A表示有向图逆图的邻接矩阵，即原图中如果有第i个结点到第j个结点长度为1的路径，则A中第j行第i列为1；
第i个结点和第j个结点引出的边，可以同时终止于某些结点，这些结点的个数为AA中第i行第j列的元素值。
从某些结点引出的边，可以同时终止于第i个结点和第j个结点，这
TTTT些结点的个数为AA中第i行第j列的元素值。
A?AT中第i行第j列对应元素为1表示从第i个结点和第j个结点
引出的边，可以同时终止于某些结点；为0表示第i个结点和第j个结点引出的边，不可以同时终止于某个结点。 4. 对于nxn的布尔矩阵A，试证明：
(I?A)(2)?(I?A)?(I?A)?I?A?A(2)
其中I是nxn的单位矩阵，并且有A(2)?A?A。再证明：对于任何正整数n?I?,都有(I?A)(n)?I?A?A2?????A(n)
证明：（1）(I?A)(2)?(I?A)o(I?A)，若该矩阵中的aij?1, 则存在vk使得aik?1且akj?1，即(I?A)?(I?A), 故(I?A)(2)?(I?A)?(I?A)。又
I?A?A，A?I?A (因为I相当于每个顶点到自己的边，不改变该顶
点到其他顶点的边)，因此有：(I?A)?(I?A)?I2?(I?A)?(A?I)?A2=
I?A?A2, 故问题一得证。
（2）用数学归纳法证明： 当n=2时成立。
假设当n=k是成立，则有：(I?A)(k)?I?A?A(2)?????A(k) 当n=k+1时，
(I?A)(k?1)?(I?A)(k)o(I?A)
?(I?A?A(2)?????A(k))o(I?A) ?(I?A?A(2)?????A(k))?(I?A)
?((I?A?A(2)?????A(k))?I)?((I?A?A(2)?????A(k))?A) ?(I?A?A(2)?????A(k))?((I?A?A(2)?????A(k))?A)
?(I?A?A(2)?????A(k))?(A?A(2)?????A(k)?A(k?1))
?I?A?A(2)?????A(k)?A(k?1)
故命题成立。
5.给定简单有向图G??V,E,??，并且有V?n。设A是G的邻接矩阵。试证明：根据第1题中所得到的结果能够把路径矩阵表示成
P?(I?A)(n)。
证明：对于有向图的路径矩阵：P?A?A(2)?(3)?????A(n)，而对于第一题有：A?A(2)?(3)?????A(n)?I?A?A(2)?(3)?????A(n)，故有：
(I?A)(n)?I?A?A2?????A(n)，由第4题得到：P?I?A?A(2)?(3)?????A(n)，
故有：P?(I?A)(n)，得证。
6. 图7-27给出一个简单有向图。试求出该图的邻接矩阵A，并求出其路径矩阵P?A?。 解：
?0?0?A??1??0??01000??00?000010???20000?，A??01??0001??01?1000???00010??00?01001???3000?，A??00??000??00?010???00010?001??000?，
?000?010??001?000??010?，
?010?001???01000??00?00010??00???4(5)A??00001?，A??01???00001???01???01000???00P?A??A?A(2)?A(3)?A(4)?A(5) ?01011??01011???=?11011? ??01011????01011??
离散数学第二版(6-7章)
