资源描述：
《离散数学课后答案(五)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、5.1习题参考答案1.阮允准同学提供答案：解：设度数小于3的结点有x个，则有3x4+4x3+2x>2xl6解得:x>4所以度数小于3的结点至少有4个所以G至少有11个结点2.阮允准同学答案：证明：由題意可知:度数为5的结点数只能是0,2,4,6.&若度数为5的结点数为0,2,4个.则度数为6的结点数为9,7,5个结论成立。若度数为5的结点数为6,8个，结论显然成立.由上可知.G中至少有5个6度点或至少有6个5度点.3、晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边•而任一结点
2、的的边必连有另一结点，则其最多有条边与其他结点相连f因此其度数最多只有n-1条,小于结点数n.4阮同学给出证明如下：证明：设G中所有结点的度数都小于3,即每个结点度数都小于等于2,则所有结点度数之和小于等于2n,所以G的边数必小于等于n,这和已知G有n+1条边相矛盾。所以结论成立。5■试证明下图中两个图不同构.晓津证明：同构的充要条件是两图的结点和边分别存在——对应且保持关联关系。我们可以看岀,(a)图和(b)图中都有〜三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点•而(b)图中三度结点
3、关联着两个二度结点和一个一度结点f因此可断定二图不是同构的。6、画出所有5个结点3条边，以及5个结点7条边的简单图.解：如下图所示：(晓津与阮同学答案一致)7■证明：下图中的图是同构的。b(b)证明如下：在两图中我们可以看到有两图中存在结点与边的一对应关系,并保持关联关系。8、证明：下面两图是同构的.阮同学给岀证明如下：证明：找出对应关系：a—q,b—-r,cs,d-—t,eu,fvzgw,h・——x9、证明：三次正则图必有偶数个结点.阮同学证明如下：由题意可知每个结点度数都是3度，即每个结点均为奇结点，根据有
4、偶数个奇结点可知,三次正则图必有偶数个奇结点.5.2习题参考答案1、解：从A到F的初级路有：ABCF、ABEF、ADEF、ABECF.ABCEF、ADECF、ADEBCF2、晓津认为图中少了一个箭头：从VI到V2有一箭头。从V2岀发的初级回路有：V2V4V1V2.V2V3V4V1V2・1.解：若G为无向连通图，有n个结点r则G中至少有n・l条边.因为在n个结点的图中，任取一个结点为起始点，若要连通其他每个结点，则其他每个结点至少应有1度此结点则有n-1度。因此总的度数至少为2n-2度f而度数为边的2倍,可算得边
5、数为n-1.对于有向图•若是弱连通，则与无向图一样至少为若是单側连通也是如此，而强连通边数至少为n.（此题根据阮允准同学的答案更正）2.解：G・F的连通分支数一定是2，而G・V‘的连通分支数就不是定数了•有可能大于2.3.答：可以。设七个人为图中的7个结点，以他们之间有共同语言为条件画边，可以看出，七个人的结点在图中是连通的，因此这七个人间可以通过相互翻译任意交谈。4.证明如下：必要性：如果图中的任何f回路者环能包含所有结点则可知未被包含在回路内的结点不能与其他结点中的某一结点连通。这与本图是强连通的相矛盾.因
6、此必有这样一个路它至少包含每个结点一次.充分性：当G中有一个回路，它至少包含每个结点一次时,可以知道f任一结点可达其他所有结点f因此它是强连通的。7、若有简单图至多有2n个结点,每个结点度数至少为nfG是连通图.又若简单图G至多有2n个结点，每个结点度数至少为n-lf那么G是连通图吗？为什么？答：G不再是连通图，假若时，G中至多可有2个结点，而每个结点度数至少可以为0,显然这两个结点不能以下是阮同学的答案：方法一:设Vi.v2是这个简单图的任意两个结点，由已知可得,vl.v2的度数至少为n•(1)若心v2之间有
7、边，则显然vl.v2熠连通的.(2)若无边.则vl和剩下的结点中的n个结点有边相连fv2也和剩下的结点中的n个结点有边相连.因为剩下的结点最多只有2n-2个f由抽屉原理可得，至少存在一个结点，它和vl、v2都有边相连f此时vl和v2也是连通的.由(1)(2)可知，结论成立方法二:显然这个图中任意的一对结点的度数之和大于等于2n,所以这个图是汉密尔顿图f所以这个图是连通的•&证明如下：n个结点的简单无向图f连通的最低条件是有n-1条边.而e>0.5(n-l)(n-2)可得enn-l.因此G是连通的。上面的答案是错
8、误的，阮允准同学纠正如下：因为一个连通图至少要有条边f但并不是说至少有n-1条边的图一定是连通图。并且容易验证这个结论不成立.证明如下：在图G中，它的结点数为n,设v是G中任一结点，若把v去掉后，其它n-1结点，每个结点度数最多有度，因此n・l个结点之间最多只有0.5(n・l)(rv2)条边，而e>0・5(n・l)(n・2),所以至少有F边连接v和其它结点.下面我用数学归纳法进一步证明
