大学离散数学课后答案

1、P146P146 习题习题 9.19.19.1.1 解： 几何图表示如右。 deg(v1)=3 deg(v2)=4 deg(v3)=3 deg(v4)=3deg(v5)=1 deg(v6)=0 奇度数结点数为 4。 (v2,v2) 为自环；(v1,v3) 与 (v3,v1) 为平行边；(v4,v5) 为悬挂边；v5 为悬挂点；v6 为孤立点。该图为伪图。9.1.2 证： n 个结点的所有图中，完全图边数最多。每点 n-1 度，n 个点的总度数为：2m=n(n-1) m=n(n-1)/2 niiv1)deg(n 个结点的任一图的边数完全图的边数， mn(n-1)/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 度点不与其它任何结点

2、相邻，而 n-1 度点与其它任何结点相邻， 二者产生一个矛盾。 9.1.5 解：仅考虑无向图。 可构成图，图如右。 否。奇度数结点数为奇数。 否。n 个结点的简单无向图中，结点的最大度数为 n-1，5 不可。 否。后三点均与其它各点有边，故第一点也应三度。 否。后二点均与其它各点有边，故第一点至少应为二度。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 P148P148 习题习题 9.29.29.2.1 解：同构的只給出其一。补图对表皆为自补图9.2.2 解：9.2.3 解：9.2.4 解： ab f b fc e c e d dH 的补图 H 相对于 G 的补图 四点的自补图 五点的自

3、补图 不存在 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 证： 构造置换 f：VaVb，f= 7 5 8 9 5 10 4 3 2 110 9 8 7 6 5 4 3 2 1 经验证，(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

4、)中 2 点，(a)中 1 点对应(b)中 3 点。又在(a)中 1 点的 3 个邻接点的度数皆不超过 3 度，而在(b)中 3 点与 4 度点 4 邻接，故出现了矛盾。所以原命题成立。 9.2.7 证：因四个结点两条边的无向简单图，只有两种非同构的状态，一种是这两条边邻接，另一种是这两条边不邻接，如右图所示。所三个这样的图，必至少有两个图同构。 (a) (b)P151P151 习题习题 9.39.39.3.1 解：各举一例。 长度为 9 的迹 长度为 8 的不是径的迹 长度为 5 的圈：长度为 6 的圈 长度为 8 的圈 长度为 9 的圈：9.3.2 解： v1v2v4v1 ，v1v2v3v4v1。 删去 (v1,v2) 或 (v4,v1) 均可。9.3.3 解： 3； 2； 4 。9.3.4 解：9.3.5 证：若从 u 到 v 存在径，则因径是迹，所以从 u 到 v 存在迹。若从 u 到 v 存在迹， 迹上点不重复，则该迹即为径。 迹上有重复的点，如：uabav，则将 ba 这段路去掉，得到的仍是从 u 到v 的迹。如果还有重复结点，则继续重复作上述删除工作，直到迹上没有重复的点

5、，便得到从u 到 v 的径。 v2 v6 v2 v5v3 v7 v1 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 5 4 3 P165P165 习题习题 9.49.49.4.1 解： v1v1 0； v1v2 1； v1v3 3； v1v4 2；v1v5 6； v1v6 4； v1v7 7； v1v8 5； v9v9 0 D = 弱分图：v1,v2,v3,v4,v5,v6,v7,v8,v10，v9单分图：v1,v2,v3,v4,v5,v6,v7,v8，v5,v7,v8,v10，v9强分图：v1,v2,v3,v4,v6，v5,v7,v8，v9，v109.4.2 解：vj在 vi到 vk的短程线上。9.4.3 反证：假设两个奇度数结点 u 和 v 之间无路则结点 u 和 v 必分居于两个不同的连通分支中，于是 u 所在的连通分支中，奇度数结点的数目为 1，与定理 9.1-1 的推论 1 矛盾！9.4.4 见 P172，定理 9.18 的证明。9.4.5 反证：假设 (G)0。设 |V|=n。任取一点， (G)0， 该点至少有一入度。沿提供入度的边反向走到该边的起点。又因该点也至少有一入度，再沿提供入度的边反向走到该边的起点。如此走下去，不外乎两种结果： 再向前走便回到已走过的点上，形成回路。 一路上走全了所有点，但因最后一点仍有入度，再向前走必然回到已走过的点上，形成回路。两种情况都存在回路，与前提无回路矛盾。 P168P168 习题习题 9.59.59.5.1 解： 3 条。 0 条。 路 65 条。其中回路 15 条。0010101011001010A9.5.2 解： 强分图为：v1，v2,v3，v4,v5。1111111111001110011100001P

《大学离散数学课后答案》由会员nt****6分享，可在线阅读，更多相关《大学离散数学课后答案》请在金锄头文库上搜索。