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

弱分支3个，分别是{v9},{v10},{v1,v2,v3,v4,v5,v6,v7,v8}

4．设v1v2v3是任意无向图（有向图）G的三个任意结点，以下三个公式是否成立？如果成立，给出证明；如果不成立，举出反例。 （1）d(v1,v2)?0，并且等号成立，当且仅当v1?v2。 解：成立。当v1?v2时，距离必定大于1。 （2）d(v1,v2)?d(v2,v1)

解：成立。因为无向图是无方向的。

5. 证明：有向图的每个结点和每条边恰处于一个弱分支中。 反证法：若任意结点V处于两个或两个以上的弱分支中，不妨设两个弱分支为G1, G2, 则G1, G2是G的极大联通子图。设v?G1,v?G2，又G1,G2?G,故G1,G2联通。这与G1, G2是极大联通子图矛盾，故命题得证。

6. 有向图的每个结点（每条边）是否恰处于一个强分支中？是否恰处于一个单向分支中？

解：有向图中的每个结点处于一个强分支中，而边不一定。有向图的结点和边可能出现在两个单向分支中。图见书上（P141 图7-18） 7. 证明同阶的回路必同构。

证明：同阶表明两个图的顶点个数相同，设为V; 又联通二度正则图称为回路。即两个图的每个顶点的度数相同为2. 边数为2V/2 = V,相同。由于两个图的顶点数，边数相同，且每个顶点的度数均为2，故两个图同构。

?(v)?1,则G恰9. 设G是弱联通有向图，如果对于G的任意结点v, dG有一条有向回路。试给出证明。

证明：因为G是弱联通有向图，不妨设一条极大单向联通子图：

?(v)?1, 所以对Vk，?e??Vk,V?。若V?V1???Vk?1，则与极大联因为: dG通子图矛盾，故V必为V1???Vk?1之一。

又假设有两条以上的回路（反证法），不妨设有两条，则这两条回路上所有点的出度为1，而要使这两条回路联通，则至少其中有一个点

?(v)?1矛盾。故G恰有一条会向回路。 的出度大于1，这与dGV1V2Vk?1Vk

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???2?2??2?至少存在一个与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???0111??012??03A??0011?001?22???0101??，A2??2?0111??2?,A3??01?0212???,A4??04?03?0100????0011????0202????012.

解：（1）对于n=1,2,…,6，试计算矩阵An1中的各元素。

??001110??211??5?000011??311120111???425?2222A1?100100????102120??5251???101010?，

A2311?，

A32??1???211?1???5254?110101??112141??7527?010010????110112????232223?13?23?? 22??72?53?22??72?，

?45?52???17?9??9A14???16?13??916139?84997??4109144?，?9917139?91413249??74998?99?38?22??33A15???39?51??222233395122?1618223317??1818332618??2233385122?3326514433??1718223316?，

??123737712212173??735044737749?A6?7744667710244??1???122737712312173?

???1217710212116877??734944737750??2）

??0001100??1100??0000011??2010200000??001000????1010100??A1?02??1010100???，A22???1003100?? ?1001000??1011200??0100000?????0000011???0100000????0000011????2014300??70?0000022??46600?0400000??003100???A3?12??4032400??4032400????，A42???60211600?? ?3014200??6046700??0200000?????0000022??0200000?????0000022????1206171300??1731290?0000044??300080000?0211600???1114170A5?62??17011141700????，A6?1702??3101445310?1306171200??291731300?0400000?0????000004?0400000????0000043）试求出图中G1和G2中的所有基本循环。

0?0?0??0?? 0?4??4??（（