资源描述：
《离散数学第9章习题答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、习题91.设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。证明：（1）先证结论：因为G是简单图，所以G的结点度上限max(d(v))≤n-1,G图的总点度上限为max(Σ(d(v))≤n﹒max(d(v))≤n(n-1)。根据握手定理，G图边的上限为max(m)≤n(n-1)/2,所以。（2）=〉G是完全图因为G具有上限边数，假设有结点的点度小于n-1,那么G的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G的每个结点的点度都为n-1，G为完全图。G是完全图=〉因为G是完全图，所以每个结点的点度为n-1,总度数为n(n-1)，根据握手定理，图G
2、的边数。■2.设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）≥3。证明：反证法，假设,则G的总点度上限为max(Σ(d(u))≤2n，根据握手定理，图边的上限为max(m)≤2n/2=n。与题设m=n+1，矛盾。因此，G中存在顶点u，d（u）≥3。■3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来:（1）（3，2，0，1，5）；（2）（6，3，3，2，2）（3）（4，4，2，2，4）；（4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。可以按如下方
3、法构造满足要求的图：序列中每个数字ai对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明：(6,3,3,2,2)对应图G的点集合V={v1,v2,v3,v4,v5}v1v5v33v4v2每个结点对应的环数(6/2,(3-1)/2,(3-1)/2,2/2,2/2)=(3,1,1,1,1)18v1v5v33v4v2将奇数3，3对应的结点v2,v3一组，画一条连线v1v5v33v4v2其他序列可以类式作图，当然大家也可以画图其它不同的图形
4、。■4．证明：在（n，m）图中。证明：图的点度数是一组非负整数{d(v1),d(v2)…d(vn)}，那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。对应到图的术语及为：最大值为，最小值为δ，平均值=(d(v1)+d(v2)…+d(vn))/n=2m/n,所以。■5．证明定理10.2。【定理10.2】对于任何（n,m）有向图G=（V，E），证明：有向图中,每条有向边为图贡献一度出度，同时贡献一度出度，所以总出度和总入度相等，并和边数相等。因此，上述关系等式成立。■6．设G是（n，m）简单二部图，证明：。证明：本题目，我们只需要说明n阶的简单二部
5、图的边数的最大值=即可。设n阶的简单二部图，其两部分结点集合分别为V1，V2,那么
6、V1
7、+
8、V2
9、=n。此种情况下，当G为完全二部图时，有最多的边数，即max(m)=
10、V1
11、
12、V2
13、,变形为，max(m)=(n-
14、V2
15、)
16、V2
17、.此函数的最大值及为n阶二部图的边的上限值，其上限值为当
18、V2
19、=n/2时取得。及max(max(m))=,所以n阶二部图(n,m),■187.无向图G有21条边，12个3度数结点，其余结点的度数均为2，求G的阶数n。解：根据握手定理有：21=(3Χ12+2(n-12))/2,解此方程得n=15■10．判断图10.29中的两个图是否同构，并说
20、明理由。图10.29解：题中两个图不同构，因为左边图的唯一3度点有2个1度点为其邻接点，而右图唯一的3度点只有1个1度点为其邻接点。因此这两个图不可能同构■13.设有向图D=如下图10.31所示。(1)在图中找出所有长度分别为1，2，3，4的圈(至少用一种表示法写出它们，并以子图形式画出它们)。(2)在图中找出所有长度分别为3，4，5，6的回路，并以子图形式画出它们。解：(1)C=AAC=ADAC=Ae4Be7Ce5AC=Ae4Be8Ce5AC=Ae4Be7Ce6De2AC=Ae4Be8Ce6De2A(2)子图略18长度为三的回路：Ae1Ae1Ae1A,Ae1
21、Ae3De2A,Ae4Be7Ce5A,Ae4Be8Ce5A长度为四的回路：AAAAA，AAADA，AABe7CA,AABe8CA,ABe7CDA,ABe8CDA长度为五的回路：AAAAAA,AAAADA,AAABe7CA,AAABe8CA,AABe7CDA,AABe8CDA,AADADA,AAAe4Be7Ce5A,AAAe4Be8Ce5A,ADAe4Be7Ce5A,ADAe4Be8Ce5A■15.若u和v是图G中仅有的两个奇数度结点,证明u和v必是连通的。证明：反证法，假设u和v不连通，那么他们必然分布于此图的两个连通分支中。那么它们将分
