欢迎来到天天文库
浏览记录
ID:15886083
大小:846.00 KB
页数:141页
时间:2018-08-06
《4 离散数学习题解答习题六(第六章 图论)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、离散数学习题解答习题六(第六章图论)1.从日常生活中列举出三个例子,并由这些例子自然地导出两个无向图及一个向图。[解]①用V代表全国城市的集合,E代表各城市间的铁路线的集合,则所成之图G=(V,E)是全国铁路交通图。是一个无向图。②V用代表中国象棋盘中的格子点集,E代表任两个相邻小方格的对角线的集合,则所成之图G=(V,E)是中国象棋中“马”所能走的路线图。是一个无向图。③用V代表FORTRAN程序的块集合,E代表任两个程序块之间的调用关系,则所成之图G+(V,E)是FORTRAN程序的调用关系图。是一个有向图。2.画出下
2、左图的补图。图[解]左图的补图如右图所示。v1′v2′v3′v4′v5′v6′v6v13.证明下面两图同构。图G′图Gv5v4v3v2[证]存在双射函数j:V→V′及双射函数y:E→E′j(v1)=v1′j(v1,v2)=(v1′,v2′)j(v2)=v2′j(v2,v3)=(v2′,v3′)270j(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,v
3、4)=(v1′,v4′)j(v2,v5)=(v2′,v5′)j(v3,v6)=(v3′,v6′)显然使下式成立:y(vi,vj)=(vi,vj′)Þj(vi)=vi′∧j(vj)=vj′(1≤i·j≤6)于是图G与图G′同构。v1v2v3v4v88v78v58v68v4¢v1¢v2¢v7¢v6¢v8¢v5¢v3¢v1v2v3v4v58v1¢v2¢v3¢v4¢v584.证明(a),(b)中的两个图都是不同构的。GG′GG′图G中有一个长度为4的圈v1v2v6v5v1,其各顶点的度均为3点,而在图G′中却没有这样的圈,因为它中
4、的四个度为3的顶点v1¢,v5¢,v7¢,v3¢不成长度的4的圈。图G′中有四个二度结点,v6¢,v8¢,v4¢,它们每个都和两个三度结点相邻,而G中一个区样的结点都没有。在(b)中,图G¢中有一2度结点v3¢,它相邻的两个项点v2¢,v4¢的度均为4,而在图G中却没有这样的点。5.一个图若同构于它的补图,则称此图为自补图。在满足下列条件的无向简单图中:1)给出一个五个结点的自补图;2)有三个或一结点的自补图吗?为什么?3)证明:若一个图为自补图,则它对应的完全图的边数不清必然为偶数。270[解]1)五个结点的自补图如左图
5、G所示GGbedcaaebcd同构函数j:V→V及y:E→如下:j(a)=ay(a,b)=(a,c)j(b)=cy(b,c)=(c,e)j(c)=ey(c,d)=(e,d)j(d)=by(d,e)=(b,d)j(e)=d(e,a)=(d,a)2)(a)没有三个结点的自补图。因为三个结点的完备图的边数为=3为奇数,所以由下面3)的结论,不可能有自补图。(b)有五个结点的自补图。1)中的例子即是一个五个结点的自补图。3)证:一个图是一个自补图,则它对应的完全图的边数必为偶数。因为若一个图G是自补图,则G∪=对应的完全图,而且E
6、∩=φ,G现同构,因此它们的边数相等,即
7、E
8、=
9、
10、,因此对应的完全图的边数
11、E*
12、=
13、E
14、+
15、
16、=2
17、E
18、,是偶数。实际上,n个项点(n>3)的自补图G,由于其对应的完全图的边数
19、E*
20、=,因此有=2
21、E
22、,为偶数。这里n≥4。对于所有大于或等于4的正整数,都可表达成n=4k,4k+1,4k+2,4k+3的形式,这里k=1,2,…。其中只有n=4k,4k+1,才能使为偶数,所以自补图的项点数只能是4k或4k+1形式,(k∈N)6.证明在任何两个或两个以上人的组内,总存在两个人在组内有相同个数的朋友。270[证]令上述组内
23、的人的集合为图G的项点集V,若两人互相是朋友,则其间联以一边。所得之图G是组内人员的朋友关系图。显然图G是简单图,图中项点的度恰表示该人在组内朋友的个数,利用图G,上述问题就抽象成如下的图认论问题:在简单图G中,若
24、V
25、≥2,则在G中恒存在着两个项点,v1,v2∈V,使得它们的度相等,即deg(v1)=deg(v2)。其证明如下:若存在着一个项点v∈V,使得deg(v)=0,则图G中各项点的度最大不超过n-2。因此n个项点的度在集合{0,1,2,…,n-2}里取值,而这个集合只有n-1个元素,因此,根据鸽笼原理,必有两个项
26、点的度相同。若不存在一个度为零的项点,则图G中各项点的度最大不超过n-1。因此n个项点的度在集合{1,2,…,n-1}中取值,这个集合只有n-1个元素,因此,根据鸽笼原理,必有两具项点的度相同。ADEFCB7.设图G的图示如右所示:1)找出从A到F的所有初级路;2)找出从A到F的所有简单路;3)求由A到
此文档下载收益归作者所有