《离散数学》刘任任版第五章

《《离散数学》刘任任版第五章》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、习题五1.请举出5个日常生活中可以用图来描述的实例.解:若V(G)表示中国的城市集合，E(G)表示城市间的道路集合，e表示U城到v城的道路，^代表0o(e)=Uv这种关联函数全体，则所定义的阁G是屮内的交通阁。类似地可定义国内的通讯网络图，某城居民的亲属关系图，比赛屮的比赛关系图，图节馆的藏书分类图等。2.设G(p，d是简单二分图，求证：q

2、%

3、=州，

4、V2

5、=,不妨设贝ijq

6、-m2=4-(4--)242因为(f-m)2>0,所以23.设G(p,以是简单阁，求证：在什么情况下，t/=l/2p(p-l)?分析：利用简单图G(p，q)的边数简单完全图G[p，q)的边数即可有下述解。解：因G(p，0是简单图。所以G屮任意两颗点之间最多只有一条边。故qSC2p=p(p-)/2。所以当为完全图时，有g二；7(厂一1)/2。4.试画出卩q个顶点的所有非同构的简单图。解:共有11个。.如下图所示。OOPluu分析：利用图的同构和无标记图的定义即可有如下解。⑼⑵⑶(10)(11)(4)⑻5.证明图5.14中的两个图是

7、同构的，图5.15巾的两个图不是同构的.试M，图5.16中的两个图是否同构？分析：利用阁同构的定义可判断。解：(1)如下图所示，令识(x)=x*其中xe｛a，b，c，d，e，f，g，h，i，j｝，x'e[abcdej'｝则可判断两图是同构的。(6z)图(2)如下图，若两图同构，则对任何双射，(p(a,b,c,d,e)=(x,y,w,v,w)必有识(6T)=W,于是推出识⑻=y，识(/?)=V，但b与V的不同，所以⑻与(b)不同构。图5.15(3)图5.16巾两个图是同构。如下图所示，4*

8、，d，e，f，g}，xe{a'，b’，c'，d’，e’，f'，g'}则可判断两图是同构的。6.设是简单图，.目.G三G求证p三0或1(mod4).分析：两个图同构的话，则它们的边数应该相等；又一个图同它的补图的边的和等于完全图的边数。证明:vGaG,:.E(G)=E(G)fi

9、£(G)

10、+

11、£(G)卜去p(p-1)。于是

12、£⑹1+而卜士厂什-1}。显然

13、£⑹

14、是整数。于是厂或厂-1是4的倍数。因此，/)三0或/)三1(mod4)。7.构造一个简单图G，使得G三G.分析：由第6题结论有广三0或定p=5,可得如下得图G及其G的补图

15、&G解：如下图G，令fgU=1，2,3,4,5,G18.求证:对任何图有:^(G)<2^/p

16、设6/(v,.)=0,则G(p，g)中存在孤立点v,.;(2)设-1，则G(p,g)中无顶点v满足t/(v)=0，此与(1)矛盾。总之,0和厂一1不能同吋岀现。由抽屉原理知，必有V,.，V,.eV(G),z>j,使J(v,.)=d(v.)08.求证：在图G(/;，p+l)中，至少有一个顶点z>，满足冲>)23.分析：利用图中所有顶点的度之和等于边的两倍可证。证明：若对任意vev(G)，均有t/(v)<2,则有2(厂+1)=2q=幺2P即2(厂+1)仝2p，也即厂+1#>。从而丨仝0,矛盾。故存在vev(G)，使t/(v)>3。9.

17、求证：在任何有2)个人的人群中，至少有两个在其中拾有相同个数的朋友.分析：作一个阶简单图G，77个顶点分别表示77个人。两个人是朋友当且仅当表示这两个人的顶点邻接。这样，问题就转化成G中至少有两个顶点的度数相等。此结论题9已证。10.求证：每一个p阶简单图G，都与~的子图同构.证明：因任何一个p阶简单图又G三G。故结论成立。11.求证：任何完全图的每个点导山子图仍是完全图.证明：由点导出子图的定义及完全图的结构即知结论成立。12.求证：二分图的每个顶点数不小于2的子图仍是二分图.分析：利用二分图及子图的概念可证。证明：设G=G(y

18、，V2)，//《G，且

19、V(H)g2。令V>{wgV(H)ueV,},V；={vgV(//)

20、vgV2}o显然，V/WXuV//，且V；nV；=0o因此，H=/y(V1,uV；)o13.设是简单图，整数/z满足求证：若p>4,且G的所有h个顶点的