1、离散数学离散数学习题集习题集第五章第五章 图与子图图与子图1/502、设、设G（p,q）是简单二分图）是简单二分图求证：求证：。2/503、设、设G（p,q）是简单图）是简单图,求证求证:qp(p-1)/2，在什么情况下，在什么情况下,q=p(p-1)/2?证实：因是简单图。所以G中任意两颗点之间最多只有一条边。故。l当G为完全图时，有q=p(p-1)/2。3/504、试画出四个顶点全部非同构简单图、试画出四个顶点全部非同构简单图.l共有11个。即4/505、证实图、证实图5.14中两个图是同构中两个图是同构,图图5.15中两中两个图不是同构个图不是同构.试问试问,图图5.16中两个图是否同中
2、两个图是否同构构?agfhebdcji5/501.令，6/50l（2）以下列图，若(a)与(b)同构，则对任何双射，l必有。于是推得l但d(b)d(v)，故(a)与(b)不一样构。bedacwxvyu7/50(3)下面两个图是同构。令,fgabcde8/506、设、设G（p,q）是简单二分图，且）是简单二分图，且 ,求证求证 .lG,且l于是|E(G)|=p(p-1)/4。l显然|E(G)|是整数。于是P或P-1是4倍数。l所以，或。或9/507、结构一个简单图、结构一个简单图G,使得使得 .l以下列图，令，l则有 .10/508、求证、求证:对任何图对任何图G（p,q）,有有:l而ll所以l
3、即11/509、设、设G（p,q）是简单图）是简单图,p2.求证求证:G中最少有两个顶点度数相等中最少有两个顶点度数相等.证实：假设G（p,q)中任何顶点度均不相等,则p个顶点度分别为0,1,2,p-1。（1）设，则中存在孤立点；（2）设，则中无顶点v满足，此与（1）矛盾。总之，0和p-1不能同时出现。由抽屉原理知，必有，使。12/5010、求证、求证:在图在图G（p,p+1）中）中,最少有一个最少有一个顶点顶点v,满足满足d(v)3.证实：若对任意，都有，则有即，也即。从而，矛盾。故存在，使。13/5011、求证、求证:在任何有在任何有n(n2)个人人群中个人人群中,最少最少有两个人在其中恰
4、有相同个数朋友有两个人在其中恰有相同个数朋友.l证实：作一个n阶简单图，n个顶点分别表示n个人。两个人是朋友当且仅当表示这两个人顶点邻接。这么，问题就转化成中最少有两个顶点度数相等。此结论题9已证。14/5012、求证、求证:每一个每一个p阶简单图阶简单图G,都与都与Kp子图同构子图同构.证实：因任何一个P阶简单图GKp。又。故结论成立。15/5013、求证、求证:任何完全图每个点导出子图仍是任何完全图每个点导出子图仍是完全图完全图.l证实：由点导出子图定义及完全图结构即知结论成立。16/5014、求证、求证:二分图每个顶点数大于二分图每个顶点数大于2子图仍是子图仍是二分图二分图.l证实：设，
5、且。令，显然，且。所以。17/5015、设、设G（p,q）是简单图，整数）是简单图，整数n满足满足1 n p 1,求证求证:若若p 4,且且G全部全部n 个顶点导出子图都有相个顶点导出子图都有相同边数同边数,则则 或或 .l证实：若和均不成立，则存在使得u与v邻接，而w与x不邻接。于是取n=2，则与边数不相同，矛盾。故或。18/5016.(1)设设G（p,q）是连通图，求证）是连通图，求证:G最少有最少有p 1条边条边;l证实：对p用归纳法a)p=1时，显然成立。b)假设对于小于p自然数，结论成立。c）在p阶连通图中任取一个顶点v。设G-v共有k个分支，且每个分支有Pi个顶点，lPi p 1,
6、则则G 中必含回路中必含回路;证实：设。若G不含回路，则必有满足。于是仍连通且无回路，而恰有条边。如此下去，连通无回路且恰含条边，一个顶点，此时是一个平凡图。从而即。此与矛盾。故G必含回路。20/5016.(3)设设G（p,q）是连通图，求证）是连通图，求证:若若q=p 1,则则G最少有两个悬挂点最少有两个悬挂点.证实：设，若对任何，都有，则，即。此与矛盾。故G中最少有一个悬挂点.。又若G中最多只有一个悬挂点，则即。从而得出（矛盾）。故G中最少有两个悬挂点。21/5017、求证、求证:若边若边e 在图在图G一条闭链中一条闭链中,则则e 必必在在G 一条回路中一条回路中.证实：设，G中含e闭链为
7、。若E不是回路，则必有。（因为回路定义是：没有重复点）从E中去掉，得到仍为闭链。如此下去，就可得到含回路。22/5018、求证、求证:对于图对于图G(p,q),若若 ,则则G中必中必含回路含回路.证实：G中无悬挂点。任取，设v1与v0邻接。如此下去，可得G中一条链又因G是有限图,由此可得一条闭链，由第题证实过程可知，故此链上必有回路。23/5019、设、设G（p,q）是简单图，且）是简单图，且 ,求证求证:G是连通图是连通图.证实：若G不连通，则可将V(G)划分成V1,V2，使得V1中顶点与V2中顶点不邻接。令，于是，且()24/5025/50即矛盾！故连通。26/50另解：另解：l考虑。则有
8、l（因为p(p-1)/2是完全图边数）即不连通，于是，G连通。27/5020、对于、对于 p 1,作一个作一个 非连通非连通图图 .证实：令。作以下，故G不连通。28/5021、（1）证实：若证实：若(p,q)是简单图，且是简单图，且 ,则则G 连通连通.证实：（1）设。若G不连通，则G顶点可划分成两个集合，使得V1与V2中顶点互不邻接。不妨设，则。由G是简单图知，(因为)从而矛盾。故G必连通。29/5021、（、（2）当）当p 为偶数时为偶数时,作一个非连通作一个非连通k 正则简单图正则简单图,其中其中 l取p=6。则。l作非连通图G以下：30/5022、证实、证实:若若eE(G),则则 证
9、实：因G任意一条边e最多联结G-e两个分支。故31/5023、证实、证实:对图对图G中任意三个顶点中任意三个顶点u,v和和w,d(u,v)+d(v,w)=d(u,w)。证实：若d(u,v)+d(v,w)d(u,w)，则与距离概念不符。（因为距离定义是：连接两点之间最短路径长度）故结论成立。32/5024、设、设G是简单连通非完全图是简单连通非完全图,求证求证:G中存在中存在三个顶点三个顶点u,v和和w,使使uv,vwE(G),但但uw E(G)。证实：证实：反证法。反证法。若不然，即对任意若不然，即对任意 ，只要只要 ，就有就有 ，也即，也即 且且 .（1）今今任任取取 。由由G连连通通知知，
10、存存在在 -通路：通路：33/50于是由（1）可知：且且且从而推得简单图G中任何两个顶点均邻接，即G是一个完全图。此与题设矛盾。34/5025、证实、证实:若若G是简单图是简单图,且且 ,则则G中中有一条长度最少是有一条长度最少是 回路回路.证实：不妨设连通（不然可对其分支进行讨论）。于是，即G中最少有个顶点。设是G中一条极长通路，则v1不与P以外任何顶点邻接。（假如存在就与P是极长通路矛盾）又因。所以存在P上个顶点均与v1邻接。于是有回路，显然。35/5026、求图、求图5.17关联矩阵和邻接矩阵关联矩阵和邻接矩阵.36/50邻接矩阵为：邻接矩阵为：=1101101101021120)(43
11、214321vvvvvvvvGA37/5027、设、设G是简单图是简单图,M(G)和和A(G)分别是分别是G关联矩阵和邻接矩关联矩阵和邻接矩阵阵.(1)求证求证:M(G)中每列各元素之和为中每列各元素之和为2.（2）A(G)各列元素之和是什么各列元素之和是什么?（1）证实：因每条边恰与两个端点u,v关联；（2）若上无环，则所在列（行）各元素之和为，不然所在列（行）各元素之和为。38/5028、设、设G是二分图是二分图,求证求证:能够将能够将G顶点作适当排列顶点作适当排列,使得使得G邻接矩阵邻接矩阵M(G)形如形如其中其中:A21是是A12转置转置.证实：因为G是二分图，所以G中无环，设。令则其
12、中;且。39/5029、设、设G是一个图是一个图(1)怎样从怎样从 得到得到 和和?(2)怎样从怎样从 得到得到?解：（1）对每个,将中所在列元素全置为0，则得；（2）对每个，将中所在行元素全置为0，则得到；（3）对每个，将中所在行与列元素全置为0，则得到；40/5030、在图、在图5.18中中,找出从找出从U1到各个顶点最短到各个顶点最短通路长度通路长度,并给出从并给出从U1到到U11最短通路最短通路.迭代WD2D3D4D5D6D7D8D9D10D11初始128111,44281021,4,22831031,4,2,55861051241,4,2,5,888610121451,4,2,5,8
13、,66710121461,4,2,5,8,6,339121471,4,2,5,8,6,3,771210148101011149991341/50l最终得D2=2，D3=7，D4=1，D5=3，D6=6，D7=9,D8=5，D9=11，D10=10，D11=13。l其中U1到U11最短通路为：I234567891011Pi1612535107942/5031、求图、求图5.19所表示图所表示图G中任意两个顶点最中任意两个顶点最短通路长度短通路长度,并给出从并给出从V1到到V3最短通路最短通路.43/5044/5045/5046/5047/5048/5049/50l其中V1到V3最短通路为：。50/50
