《大学离散数学课后结果解析》由会员分享，可在线阅读，更多相关《大学离散数学课后结果解析（17页珍藏版）》请在金锄头文库上搜索。
1、P146 习题 9.19.1.1 解： 几何图表示如右。 deg(v 1)=3 deg(v2)=4 deg(v3)=3 deg(v4)=3deg(v5)=1 deg(v6)=0 奇度数结点数为 4。 (v 2,v2) 为自环；(v 1,v3) 与 (v 3,v1) 为平行边；(v4,v5) 为悬挂边；v 5 为悬挂点；v 6 为孤立点。该图为伪图。9.1.2 证： n 个结点的所有图中，完全图边数最多。每点 n-1度，n 个点的总度数为：2m= =n(n-1) m=n(n-1)/2niiv1)deg(n 个结点的任一图的边数完全图的边数， mn(n-1)/2 在简单有向完全图中，任二点之间有两
2、条方向相反的边， 每点的度数为 2(n-1)， 总度数为 2m=2(n-1)n， m=n(n-1)。 9.1.3 解： 去掉 v 点后，有 n-1 个结点，m-d 条边。 去掉 e 边后，有 n 个结点，m-1 条边。9.1.4 证：假设 n个结点的度数皆不相同 在简单无向图中，一个结点的最大度数为 n-1，最小度数为 0。 它们只能为 0，1，n-1 n 个值。 0 度点不与其它任何结点相邻，而 n-1度点与其它任何结点相邻， 二者产生一个矛盾。 9.1.5 解：仅考虑无向图。 可构成图，图如右。 否。奇度数结点数为奇数。 否。n 个结点的简单无向图中，结点的最大度数为 n-1，5 不可。
3、否。后三点均与其它各点有边，故第一点也应三度。 否。后二点均与其它各点有边，故第一点至少应为二度。9.1.6 解：2m=nk m=nk/2 。9.1.7 证： 当图 G中 n个点的度数都为 (G)时，总度数为 2m=n(G)。但一般情况下，(G) 为最小度数，而并非所有结点的度数都为 (G)时，必有 2mn(G)， 2m/n (G) 。 当图 G中 n个点的度数都为 (G)时，总度数为 2m=n(G)但一般情况下，(G) 为最大度数，而并非所有结点的度数都为 (G)时，必有 2mn(G)， 2m/n(G) 。 V1V3 V2V5 V4V6 P148 习题 9.29.2.1 解：同构的只給出其一
4、。 补图对表 皆为自补图9.2.2 解：9.2.3 解：9.2.4 解： ab f b fc e c e d dH 的补图 H 相对于 G 的补图 四点的自补图 五点的自补图 不存在 3个结点或 6个结点的自补图，因为他们的完全图边数为奇数。 证明：设结点数和边数分别为 n和 m。有 n个结点的自补图，则 n个结点的完全图边数必为偶数, m=2t tI + ，又 完全图边数 m=n(n-1)/2， n(n-1)=4t ；若 n为偶数，则 n-1必为奇数， n 必为 4的倍数， n=4k，kI + ，若 n为奇数，n 必为 4的倍数， n-1=4k， n=4k+1，kI + 。 9.2.5 证：
5、 构造置换 f：V aV b，f= 7 589 10 326 经验证，(x,y) Ea，(f(x),f(y) Eb，反之亦然。根据同构的定义，两图同构。 9.2.6 证：假设两图同构，根据前面介绍的两途同构的必要条件，在(a)中只有 1和 2两点间有平行边，在(b)中只有 2和 3两点间有平行边，所以必然是(a)中的 1和 2两点与(b)中的 2和 3两点相对应。又因在(a)中 1点 4度，2 点 3度，在(b)中 2点 3度，3 点 4度，所以必然是(a)中 2点对应(b)中 2点，(a)中 1点对应(b)中 3点。又在(a)中 1点的 3个邻接点的度数皆不超过 3度，而在(b)中 3点与
6、4度点 4邻接，故出现了矛盾。所以原命题成立。 9.2.7 证：因四个结点两条边的无向简单图，只有两种非同构的状态，一种是这两条边邻接，另一种是这两条边不邻接，如右图所示。所三个这样的图，必至少有两个图同构。 (a) (b)P151 习题 9.39.3.1 解：各举一例。 长度为 9的迹 长度为 8的不是径的迹 长度为 5的圈：长度为 6的圈 长度为 8的圈 长度为 9的圈：9.3.2 解： v 1v2v4v1 ，v 1v2v3v4v1。 删去 (v 1,v2) 或 (v 4,v1) 均可。9.3.3 解： 3； 2； 4 。9.3.4 解：9.3.5 证：若从 u到 v存在径，则因径是迹，所
7、以从 u到 v存在迹。若从 u到 v存在迹， 迹上点不重复，则该迹即为径。 迹上有重复的点，如：uabav，则将 ba这段路去掉，得到的仍是从 u到v的迹。如果还有重复结点，则继续重复作上述删除工作，直到迹上没有重复的点，便得到从u到 v的径。 v2 v6 v2 v5v3 v7v1 v10 v1 v7v4 v8 v3 v5 v9 v4 v6 L=4 L=101 8 6 2 7 9 10 5 4 3 1 8 6 2 7 9 10 5 4 3 1 8 6 2 7 9 10 5 4 3 1 8 6 2 7 9 10 5 4 3 1 8 6 2 7 9 10 5 4 3 1 8 6 2 7 9 10
8、5 4 3 P165 习题 9.49.4.1 解： v 1v 1 0； v 1v 2 1； v 1v 3 3； v 1v 4 2；v1v 5 6； v 1v 6 4； v 1v 7 7； v 1v 8 5； v 9v 9 0 D = 弱分图：v 1,v2,v3,v4,v5,v6,v7,v8,v10，v 9单分图：v 1,v2,v3,v4,v5,v6,v7,v8，v 5,v7,v8,v10，v 9强分图：v 1,v2,v3,v4,v6，v 5,v7,v8，v 9，v 109.4.2 解：v j在 vi到 vk的短程线上。9.4.3 反证：假设两个奇度数结点 u和 v之间无路则结点 u和 v必分居
9、于两个不同的连通分支中，于是 u所在的连通分支中，奇度数结点的数目为 1，与定理 9.1-1的推论 1矛盾！9.4.4 见 P172，定理 9.18的证明。9.4.5 反证：假设 (G)0。设 |V|=n。任取一点， (G)0， 该点至少有一入度。沿提供入度的边反向走到该边的起点。又因该点也至少有一入度，再沿提供入度的边反向走到该边的起点。如此走下去，不外乎两种结果： 再向前走便回到已走过的点上，形成回路。 一路上走全了所有点，但因最后一点仍有入度，再向前走必然回到已走过的点上，形成回路。两种情况都存在回路，与前提无回路矛盾。 P168 习题 9.59.5.1 解： 3 条。 0 条。 路 65条。其中回路 15条。01A9.5.2 解： 强分图为：v 1，v 2,v3，v 4,v5。11P 1001TP9.5.3 解： e 1 e2 e3 e4 e5 e6v1 -1v2 1 1 -1v3 -1 1 -1v4 1 1 -1v5 -1 1 deg in(v1)=1；deg out(v1)=0；d
