================精选公文范文，管理类，工作总结类，工作计划类文档，欢迎阅读下载==============
图的所有结点的度数都大于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 ~