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???2?30123?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，可以对结点的环路进行分解，分解为多个小的环路的并。
7.6第186页
1.图7-34是不是二部图？如果是，找出其互补结点子集。 解：是，互补结点子集是：{v1,v3,v5},{v2,v4,v6,v7}。 2.如何由无向图G的邻接矩阵判断G是不是二部图？
解：设G的邻接矩阵为A，V?n，计算A(2)，A(3)，…A(n)。其中如果矩阵的对角线出现了基数，则G不是二部图。如果所有的矩阵（包括矩阵A）的回路长度都是偶数，则是二部图。
3.举出一个二部图的例子，它不满足定理7.6.3的条件，但是存在完美匹配。
解：如第一题的例子，二部图为：
2 1 3 5 4 6 7 该图中不满足定理7.6.3的条件（对于V1，在V2中至少有2个结点与其相邻，但是在V2中，各结点最多有有2个结点与V1中结点相邻），但是该图是完美匹配，因为匹配数为3（=V1）（如v1v2，v3v4 ，v5v7） 4.证明：n阶简单二部图的边数不能超过[n2/4]。
证明：对于简单二部图，当为完全二部图时边数最多，边数为V1?V2，又V1?V2?n，当V1?V2即V1?V2?n/2时，V1?V2有最大值n2/4，故边数取整，故边数不能超过[n2/4]。得证。 5.
解：可能，如下图：
P1P5P6P2P3P4
6. 解：
张明王同李林赵丽数学物理电工计算机科学
7. 图7-35是否存在{v1,v2,v3,v4}到{u1,u2,u3,u4,u5}的完美匹配？如果存在，指出它的一个完美匹配。 解：存在。如：v1u2，v2u1，v3u4，v4u5。
7.7第192页
1.对于下列情况，验证欧拉公式n-m+k=2 (1)图7-45中的多边形的图。
解：对a)点数7，面的个数3，边的个数8，7+3-8=2，成立。 对b)顶点个数8，面的个数3，边的个数9，8+3-9=2，成立。 (2)一个具有(r?1)2个结点的无向边，它描述了r2个正方形的网络，例如棋盘等。
解：顶点个数为(r?1)2，面的个数为r2?1，边的个数为r2，
(r?1)2+r2?1-2r(r?1)=2，成立。
2.试证明：图7-42b中的库拉图斯基图是个非平面图。 证明：
12534 对于基本环路：v1v2v3v4v5v1,考虑v2v5和v3v5在环的内侧，直线v1v4必定在外侧。对于直线v1v3和v2v4必定相交。故该图是非平面图。 3. 画图所有不同构的6阶非平面图。
解：根据分析图至少有9条边，最多为15条边。所有情况如下图：
9910111112131415
4.试用库拉斯基定理证明：图7-48中的图是个非平面图。
离散数学第二版（6-7章）
