离散数学第二版答案（6-7章）

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个结点，这

T些结点的个数为AA中第i行第j列的元素值。

TTTA?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)(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)(I?A)

?(I?A?A(2)?????A(k))(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??7. 使给出图7-25中的有向图的距离矩阵。dij?1意味着什么？ 解：

?012????101?????D??210???, dij?1表示有一条vi到vj的边。

?????01???????10??8. 试求出第2题中的图G1和G2的距离矩阵。 解：

?0?2??1D1???1?1??2?021112????03211???230123??D?, ?2?121012??1?12101????13210????????0???11???012?????101??? ?210????1???02?1???20??2119. 如何才能从一个距离矩阵中求得一个路径矩阵呢？

证明：对于任意结点vi和vj（i?j），由题意aij?0，因此从vi到vj必定存在一条长度不为0的路径，由结点选取的任意性得：任何两个结点均是联通的。故G的强联通的有向图。

从距离矩阵求路径矩阵：将距离矩阵中不为0的值变为1，即可得到。 10. 试确定图7-25所示的图是否是强分支。 解：对图7-25由距离矩阵求得的路径矩阵为：

?0?1?P??1??0??01100?0100??1000?，由路径矩阵知该图不是强分支。

?0001?0010??

7.5第184页

1.

解：a), b), c)是欧拉图，d), e), f)不是欧拉图。

2.如果G1和G2是可运算的欧拉有向图，则G1?G2仍是欧拉有向图。这句话对吗？如果对，给出证明，如果不对，举出反例。 证明：不对,不能保证连通.

4.设G是平凡的连通无向图，证明：G是欧拉图，当且仅当G是若干个边不相交的回路的并。

证明：充分性，当进行若干个不相交的回路的并运算后，每个结点都是偶结点，因此G是欧拉图。

必要性，对于G是欧拉图，则G必定有欧拉闭路。如果某个结点的度数大于2，可以对结点的环路进行分解，分解为多个小的环路的并。