离散数学考试试题(A、B卷及答案)test7(2)

(2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？

(3)求出ATA和AAT，说明ATA和AAT中的第(2，2)元素和第(2，3)元素的意义。 (4)求出可达矩阵P。 (5)求出强分图。

解 (1)求G的邻接矩阵为：

?0??0A??0??0?101??011?

101??100??(2)由于

?0??0A2??0??0?111??02??201??01 A3???02111???02011???12??03??22??04 A4???1203???0101???23??13? 23??22??所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。 (3)由于

?0??0TAA??0??0?000??21??312??12TAA? ?21011????10213???21??10? 21??21??再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以v2为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以v2为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为1。

?0??0(4)因为B4?A?A2?A3?A4??0??0??0??0以求可达矩阵为P??0??0?111??111?。

111??111??101??0??011??0+

101??0???100???0111??0

??

201??0

+

111??0

??

?011???0212??03??122??04+

212??03???201???0123??13??23??22???0

??0?0??0?741?

?

747?

，所

747?

?

434??

?0??0(5)因为P?PT??0??0?111??0??111??1∧?1111????1111???000??0??111??0＝?0111????0111???000??111?，所以{v1}，{v2，v3，v4}构成G的强分图。

111??111?? 6

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学考试试题(A、B卷及答案)test7(2)在线全文阅读。