交大版《离散的数学结构》标准答案 下载本文

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

图的所有结点的度数都大于4,因而都大于等于5,则 §2定理1,有 2m? 故此 n≤ nn入口 u 入口 uu ?deg(v)??5?5n ii?1i?12m 5 于简单平面图无平等边,自环,所以任一区域都至少三条或以的边围成,故 利用欧拉公式的推论公式:m≤3n-6,有 m≤3· 2m?6 5因此,m≥30,这与已知条件m<30矛盾。所以,假设错误,小于30条边的简单平

面图必有一个结点的度数小于等于4。 33.在2个结点构成的r2个正方形网格所组成的平面图上,验证Euler公式 的正确性。 [证] 如此的平面图,结点数n=(r+1)2 26 边数m=(r+1)r+(r+1)r=2(r+1)r =2r2+2r 面数f=r2+1 于是 n-m+f=(r+1)2-(2r2+2r)+(r2+1)

=(r2+2r+1)-(2r2+2r)+(r2+1) =2 故此Euler公式对此类图正确。 34.运用kuratowski定理证明下图是非平面图。 [证]给图G中结点打上标

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 16 ~

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

号,并用黑点标记要删去的边。 1 6 2 7 5 3 4 图G 去

掉图G中打黑点的边,得图G的子图。 27 3 4 2 7 1 6 5 图G 图G的子图 对图G的

子图进行变形。 1 6 2 5 7 3 4 图G的子图 用kuratowski技术对图G的子图进行处理: 从而,在kwratowski技术下,与K3·3同构,因而根据Kwratowski定理,此图G是非平面

图。 1 2 5 4 3 7 28 1 离散数学习题解答 习题七 1.证明树是只有一个区域的平面图。 [证] 证法一 于树无圈套在,因此根据kuratowski定理,可知树是平面图,因此可用Euler定理。对于树,m=n-1,故此n-m+r=2,得树的区域数 r=2+m-n=2+-n=1 证法二 用归纳法,施归纳于树的结点个数n。 当n=1时,只显然为平面图只有一个区域,题意为真 当n=k时,假设题意为真。 当n=k+1时,我们来证题意为真。

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 17 ~

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

事实上,于T是树,故T中至少有一个悬挂点,在T中删去此结点,得到一个k个结点的边通图T′,显然T′中无圈。于T′是一个具有k个结点的树,于是根据归纳假设,T′是只有一个区域的平面图。这时将删去的结点重新扦入T′中以得到T,于悬挂点不改变图的平面性和区域数,因此T仍是中仍一个区域的平面图。 2.请画出具有六个结点的各种不同构的自树。 [解] 共有六种,图示如下: 3.证明任意一棵树中至少有两片叶子。 29 [证] 当结点数n≥2时,任意一棵树必至少有两片叶子。否则,假设某树中最多只有 一片叶了,那么其中n-1结点都不是叶子,故此这n-1个点的度都大于等于2,于是根据各结点的度的总

和是边数的二倍可知 2n-2=2(n-1)=2m=

n?deg(v)≥2(n-1)+1=2n-1 ,矛盾。 ii?14.在一棵树中,度数为2的结点有n2个;度数为了的结点有n3个;?;度

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 18 ~

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

数为k的 结点有nk个;问它有几个度数为1的结点? [解] 设这棵树的项点数为n,边数为m,度为1的结点数为x。从而 n=x+n2+n3+?+nk 但是 n?degv()=2m=2(n-1)=2n-2 ii?1n?degv()=1·x+2·n+3·n+?k·n i2 3 k i?1 =2(x+n2+n3+?+nk)-2 于是解得 x=n3+2n4?+(k-2)nk+2 因此,度为1的结点共有n3+2n4+?+(k-2)nk+2个。 5.设G=是连通的无向图,证明m≥n-1。 [证] 既然G是一个连通的无向图,那么G 一定包含一个生成树。 又因| V |=n,于是生成树的边数为n-1,从而 m=| E |≥n-1 6.若G=是无向图,且n≤m,则G中必有圈。 [证] 用反证法。假设G中无圈,则 当G连通时,有G是一棵树,从而m=n-1<n,与已知n≤m矛盾。 当G不连通时,有G是森林,不妨设G有k个树,每个树的结点数分别为n1,n2,?nk,边数分别是n1-1,n2-1,?,nk-1。显然总数 m=

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 19 ~

================精选公文范文,管理类,工作总结类,工作计划类文档,欢迎阅读下载==============

n?i?1ni=n 因此,G的 ?i?1n(ni-1)= ?n-?ii?1i?1nn1=n-k<n 与已知n≤m矛盾。 7.求出左上图中的全部生成树。 [解] 此图共有16个生成树,(详见王朝瑞《图论》P259 30

--------------------精选公文范文,管理类,工作总结类,工作计划类文档,感谢阅读下载---------------------

~ 20 ~