《大学离散数学课后答案》由会员分享，可在线阅读，更多相关《大学离散数学课后答案（15页珍藏版）》请在金锄头文库上搜索。
1、 V1 oV3 o o V2V5 o o V4 V6 oP6 习题。19.1.1 解：几何图表示如右. d(1）= deg（v2） deg（v3）=3 deg(v4）= dg(v5)=1 de(6）= 奇度数结点数为 . （v2，v2） 为自环;(v1，v） 与 (v3，1）为平行边; (v4，v） 为悬挂边;v 为悬挂点；v 为孤立点.该图为伪图.9。1.2 证:n个结点的所有图中，完全图边数最多. 每点-1度，n个点的总度数为：=(1) m=(n1）/2个结点的任一图的边数完全图的边数， mn(n1）/2 在简单有向完全图中，任二点之间有两条方向相反的边， 每点的度数为 2(n-），总度数
2、为 2m2（-1）n, mn(n1). 。13 解:去掉 v点后,有 n1个结点，md条边. 去掉 边后,有 个结点，m1条边.9。1.4 证：假设n个结点的度数皆不相同 在简单无向图中，一个结点的最大度数为n，最小度数为。 它们只能为 0，1， 个值。 0度点不与其它任何结点相邻，而-1度点与其它任何结点相邻, 二者产生一个矛盾。 oo o o o9。1. 解：仅考虑无向图。 可构成图，图如右. 否.奇度数结点数为奇数。 否。n个结点的简单无向图中，结点的最大度数为n1，不可。 否。后三点均与其它各点有边，故第一点也应三度。 否。后二点均与其它各点有边，故第一点至少应为二度。91.6 解：2
3、m=nk m=n/2 。9。1。7 证： 当图中n个点的度数都为 d（G）时，总度数为 m=nd(G）。 但一般情况下,d（G）为最小度数,而并非所有结点的度数都为 d(G）时， 必有 nd（G）， 2/nd（）。 当图G中n个点的度数都为 （G）时，总度数为2m=(G) 但一般情况下，（G）为最大度数，而并非所有结点的度数都为 (G）时, 必有 2mn（G）, 2m/(G) . P1 习题。29。.1 解:同构的只給出其一。 o o o o o o o oo o o o o o o o o o o o o o o o o o o o o o o oo o o o o o o o o o o
4、o o o o o 补图对表皆为自补图 a ob o o f b o o fc o o e c o o e o o d d H的补图 H相对于G的补图9。22 解:o o o o o o o o o o o oo o o o o o o o o o o oo o o o o o o o o oo o o o o o o o o o923 解： o o o o o o o o o四点的自补图 五点的自补图9.24 解： 不存在3个结点或6个结点的自补图，因为他们的完全图边数为奇数。 证明：设结点数和边数分别为n和。 有n个结点的自补图，则n个结点的完全图边数必为偶数, m2 t+ ，又完全图边数
5、 m=（n1）/2, n(n1)4 ； 若n为偶数，则n1必为奇数，必为4的倍数， 4,I+ ， 若n为奇数，n必为4的倍数， n-14k，=4k+1，kI+ 。 9.5证： 构造置换f：VV, 经验证，(x，y）a，（(x)，f(y）)Eb，反之亦然。 根据同构的定义，两图同构。 92。6 证:假设两图同构,根据前面介绍的两途同构的必要条件, 在（）中只有1和2两点间有平行边，在（b）中只有和3两点间有平行边， 所以必然是(a)中的1和两点与(b）中的2和3两点相对应。 又因在（)中1点4度,2点度，在（b)中点3度，3点度， 所以必然是（a）中点对应(b）中点,(a）中点对应(b)中3点。
6、 又在（a）中点的3个邻接点的度数皆不超过3度，而在(b）中3点与4度点邻接， 故出现了矛盾。所以原命题成立。 o o o oo o o o (a) (b).2。7 证：因四个结点两条边的无向简单图，只有两种非同构的状态，一种是这两条边邻接，另一种是这两条边不邻接,如右图所示.所三个这样的图，必至少有两个图同构。 11 习题9。9.。1 解：各举一例. 1 o 8 o 6 o 2 o 7 o 9 o 10 o5 o 4 o 3 o 1 o 8 o 6 o 2 o 7 o 9 o 10 o5 o 4 o 3 o 1 o 8 o 6 o 2 o 7 o 9 o 10 o5 o 4 o 3 o 长度
7、为9的迹 长度为8的不是径的迹 长度为5的圈 1 o 8 o 6 o 2 o 7 o 9 o 10 o5 o 4 o 3 o 1 o 8 o 6 o 2 o 7 o 9 o 10 o5 o 4 o 3 o 1 o 8 o 6 o 2 o 7 o 9 o 10 o5 o 4 o 3 o ： 长度为的圈 长度为的圈 长度为9的圈：9.3。2 解： v1v2vv1 ，v1v2v3v4v1。 删去 (v1，2） 或 (v4，v1) 均可。9。3。3 解： ； 。 v2 o o v6 v2 o o v5 v3 o o v7v1 o o v10 v1 o o v7 v4 o o v8 v3 o v5 o o v9 v4 o o v6 L=4 L=1093。 解：.3.5 证:若从u到v存在径,则因径是迹,所以从u到v存在迹。 若从到v存在迹, 迹上点不重复,则该迹即为径. 迹上有重复的点，如:uaba,则将ba这段路去掉，得到的仍是从到v的迹。如果还有重复结点，则继续重复作上述删除工作，直到迹上没有重复的点，便得到从u到v的径。 P65 习题9.49。41 解： v1v ；
