交大版《离散的数学结构》标准答案(6)

[解] 不存在{v1，v2，v3，v4}到{u1，u2，u3，u4，u5}的完美匹配。

因为这两个互补结点子集的结点个数不相同。

31．某展览会共有25个展室，布置如下图所示，有阴影的展室陈列实物，无阴影的

展室陈列图片，邻室之间均有门可通。有人希望每个展室都恰去一次，您能否为他设计一条路线？ [解] 不能。

因为，若我们将每个展室看作一个项点，并且V1是无阴影展室的项点集，V2是有阴影展室的项点集，将邻室之间的门通道看作相应两顶点的边，于是我们得到一个二分图G。从而问题转化为问图G中是否有从起点（入口）uv1到终点（出口）v∈V2的一条Hamilton路？而这样的H路存在的必须条件是| V1|=| V2|（参见29的2）证法=b))。但是|V1|=121≠3=|V2|，故不满足必要条件，所以没有从u到v的Hamilton路。 32．证明：小于30条边的平面简单图有一个结点的度数小于等于4。

[证] 用反法：假设简单平面图的所有结点的度数都大于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．在由（r+1）2个结点构成的r2个正方形网格所组成的平面图上，验证Euler公式

的正确性。

[证] 如此的平面图，结点数n=(r+1)2

26

边数m=(r+1)r+(r+1)r=2(r+1)r =2r2+2r

面数f=r2+1 （外部为-4r条边围成的面）

于是 n-m+f=(r+1)2-(2r2+2r)+(r2+1) =(r2+2r+1)-(2r2+2r)+(r2+1) =2

故此Euler公式对此类图正确。

34．运用kuratowski定理证明下图是非平面图。

[证]（1）给图G中结点打上标号，并用黑点标记要删去的边。

1 6 2 7 5

3 4

图G

（2）去掉图G中打黑点的边，得图G的子图。

27

3

4

2 7 1 6 5

图G

图G的子图

（3）对图G的子图进行变形。

1 6 2 5

7 3 4

图G的子图

（4）用kuratowski技术对图G的子图（变形后的）进行处理：

从而，在kwratowski技术下，（3）与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=1

证法二 用归纳法，施归纳于树的结点个数n。

当n=1时，只显然为平面图只有一个区域，题意为真

当n=k时，假设题意为真。 当n=k+1时，我们来证题意为真。

事实上，由于T是树，故T中至少有一个悬挂点，在T中删去此结点，得到一个k个结点的边通图T′，显然T′中无圈。于T′是一个具有k个结点的树，于是根据归纳假设，T′是只有一个区域的平面图。这时将删去的结点重新扦入T′中以得到T，由于悬挂点不改变图的平面性和区域数，因此T仍是中仍一个区域的平面图。

2．请画出具有六个结点的各种不同构的自由树。 [解] 共有六种，图示如下：

（1） （2） （3）

（4） （5） （6） 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个；?；度数为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=（V，E）是连通的（n，m）无向图，证明m≥n-1。 [证] 既然G是一个连通的无向图，那么G 一定包含一个生成树。 又因| V |=n，于是生成树的边数为n-1，从而

m=| E |≥n-1

6．若G=（V，E）是（n，m）无向图，且n≤m，则G中必有圈。 [证] 用反证法。假设G中无圈，则

（a）当G连通时，有G是一棵树，从而m=n-1＜n，与已知n≤m矛盾。

（b）当G不连通时，有G是森林，不妨设G有k个树，每个树的结点数分别为n1，n2，?nk，边数分别是n1-1，n2-1，?，nk-1。显然总数

m=

n?i?1ni=n 因此，G的

?i?1n(ni-1)=

?n-?ii?1i?1nn1=n-k＜n （k＞1）

与已知n≤m矛盾。 7．求出左上图中的全部生成树。

[解] 此图共有16个生成树，（详见王朝瑞《图论》P259

30

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库交大版《离散的数学结构》标准答案(6)在线全文阅读。