下载此文档

交大版《离散的数学结构》标准答案.doc

文档分类：研究生考试 | 页数：约35页举报非法文档有奖

1/35

下载提示

1.该资料是网友上传的，本站提供全文预览，预览什么样，下载就什么样。
2.下载该文档所得收入归上传者、原创者。
3.下载的文档，不会出现我们的网址水印。

同意并开始全文预览

(约 1-6 秒)

1/35 下载此文档

文档列表 文档介绍

离散数学辅助教材
概念分析结构思想与推理证明
离散数学****题解答,并由这些例子自然地导出两个无向图及一个向图。
[解] ①用V代表全国城市的集合,E代表各城市间的铁路线的集合,则所成之图G=(V,E)是全国铁路交通图。是一个无向图。
②V用代表中国象棋盘中的格子点集,E代表任两个相邻小方格的对角线的集合,则所成之图G=(V,E)是中国象棋中“马”所能走的路线图。是一个无向图。
③用V代表FORTRAN程序的块集合,E代表任两个程序块之间的调用关系,则所成之图G+(V,E)是FORTRAN程序的调用关系图。是一个有向图。
。

图
[解] 左图的补图如右图所示。
v1′
v2′
v3′
v4′
v5′
v6′
v6
v1
。
图G′
图G
v5
v4
v3
v2

[证] 存在双射函数j:V→V′及双射函数y : E→E′
j (v1)=v1′ j (v1,v2)=(v1′,v2′)
j (v2)=v2′ j (v2,v3)=(v2′,v3′)
j (v3)=v3′ j (v3,v4)=(v3′,v4′)
j (v4)=v4′ j (v4,v5)=(v4′,v5)
j (v5)=v5′ j (v5,v6)=(v5′,v6′)
j (v6)=v6′ j (v6,v1)=(v6′,v1′)
j (v1,v4)=(v1′,v4′)
j (v2,v5)=(v2′,v5′)
j (v3,v6)=(v3′,v6′)
显然使下式成立:
y (vi,vj)=(vi,vj′)Þ j (vi)=v i′∧j (vj)=vj′
(1≤i·j≤6)
于是图G与图G′同构。
v1
v2
v3
v4
v88
v78
v58
v68
v4¢
v1¢
v2¢
v7¢
v6¢
v8¢
v5¢
v3¢
v1
v2
v3
v4
v58
v1¢
v2¢
v3¢
v4¢
v58
(a),(b)中的两个图都是不同构的。
G
G′
G
G′
图G中有一个长度为4的圈v1v2v6v5v1,其各顶点的度均为3点,而在图G′中却没有这样的圈,因为它中的四个度为3的顶点v1¢,v5¢,v7¢,v3¢不成长度的4的圈。
图G中′有四个二度结点,v6¢,v8¢,v4¢,它们每个都和两个三度结点相邻,而G中一个区样的结点都没有。
在(b)中,图G¢中有一2度结点v3¢,它相邻的两个项点v2¢,v4¢的度均为4,而在图G中却没有这样的点。
,则称此图为自补图。在满足下列条件的无向简单图中:
1) 给出一个五个结点的自补图;
2)有三个或一结点的自补图吗?为什么?
3)证明:若一个图为自补图,则它对应的完全图的边数不清必然为偶数。
[解] 1) 五个结点的自补图如左图G所示
G
G
b
e
d
c
a
a
e
b
c
d
同构函数j : V→V及y : E→如下:
j (a)=a y(a,b)=(a,c)
j (b)=c y(b,c)=(c,e)
j (c)=e y(c,d)=(e,d)
j (d)=b y(d,e)=(b,d)
j (e)=d (e,a)=(d,a)
2)(a)没有三个结点的自补图。因为三个结点的完备图的边数为=3为奇数,所以由下面3)的结论,不可能有自补图。
(b)有五个结点的自补图。1)中的例子即是一个五个结点的自补图。
3)证:一个图是一个自补图,则它对应的完全图的边数必为偶数。
因为若一个图G是自补图,则G∪=对应的完全图,而且E∩=φ,G现同构,因此它们的边数相等,即|E|=||,因此对应的完全图的边数|E*|=|E|+||=2|E|,是偶数。
实际上,n个项点(n>3)的自补图G,由于其对应的完全图的边数|E*|=,因此有=2|E|,为偶数。这里n≥4。对于所有大于或等于4的正整数,都可表达成n=4k,4k+1,4k+2,4k+3的形式,这里k=1,2,…。其中只有n=4k,4k+1,才能使为偶数,所以自补图的项点数只能是4k或4k+1形式,(k∈N)
,总存在两个人在组内有相同个数的朋友。
[证] 令上述组内的人的集合为图G的项点集V,若两人互相是朋友,则其间联以一边。所得之图G是组内人员的朋友关系图。显然图G是简单图,图中项点的度恰表示该人在组内朋友的个数,利用图G,上述问题就抽象成如下的图认论问题:在简单图G中,若|V|≥2,则在G中恒存在着两个项点,v1,v2∈V,使得

交大版《离散的数学结构》标准答案来自淘豆网www.taodocs.com转载请标明出处.