2022年《离散数学》刘任任版 .pdf
《2022年《离散数学》刘任任版 .pdf》由会员分享,可在线阅读,更多相关《2022年《离散数学》刘任任版 .pdf(7页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、习题七1对图 7.7 中的两个图,各作出两个顶点割。解:对图 7.7 增加加节点标记如下图所示,则(a)的两个顶点割为:V11=a,b ;V12=c,d (b)的两个顶点割为:V21=u,v ;V12=y 2求图 7.7 中两个图的G和G. 解:如上两个图,有k(G1)=(G1)=2, k(G2)=1, (G2)=2 3试作出一个连通图G, 使之满足:GGG解:做连通图G 如下,于是有:4求证 , 若qpG,是k边连通的 , 则2/kpq. 证明:设 G 是 k边连通的,由定义有(G)k. 又由定理 7.1.2 知(G),因此有 k(G) 即 k,从而(a)(b)图 7.7 )(a)(b7.7
2、图dcbaxwvuypq2pq2pq2pq2。2kpq)()()(GGGk名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 7 页 - - - - - - - - - 5求证 , 若G是p阶简单图 , 且2pG, 则GG. 分析:由 G 是简单图,且2pG,可知 G 中的 (G)只能等于p-1 或 p-2;如(G)= p-1,则 G 是一个完全图,根据书中规定,有k(G)=p-1= (G);如(G)= p-2,则从 G 中任取 V(G)的子集 V1,其中 |V1|=3,则
3、V(G)-V1 的点导出子图是连通的,否则在V1 中存在一个顶点v,与其他两个顶点都不连通。则在G 中,顶点v 最多与 G 中其他 p-3 个顶点邻接,所以d(v)p-3,与(G)= p-2 矛盾。这说明了在G中,去掉任意p-3 个顶点后 G 还是连通的,按照点连通度的定义有k(G)k-3 ,又根据定义 7.1.1,GG,有 k(G)=k-2 。证明:因为G 是简单图,所以 d(v)p-1,vV(G), 已知(G)p-2 ()若 (G)= p-1,则 G=Kp (完全图),故 k(G)=p-1= (G)。()若 (G)= p-2, 则 GKp,设 u,v 不邻接,但对任意的wV(G),有uw,
4、vw E(G).于是,对任意的V1V(G), | V1|=p-3 ,G-V1 必连通 . 因此必有 k(G) p-2=(G),但 k(G) (G)。故 k(G) =(G)。6找出一个p阶简单图 , 使3pG, 但GG. 解:7设G为3正则简单图 , 求证GG. 分析: G 是一个3正则简单图,所以(G)=3,根据定理7.1.1 有)(GGG,所以G只能等于 0,1,2,3 这四种情况。下面的证明中分别讨论了这四种情况下GG 和的关系。证明: (1)若G=0,则 G 不连通 ,所以(G)=K(G). (2) 设 K(G)=1, 且 u 是 G 中的一个割点, G-u 不连通 ,由于 d(u)=3
5、,从而至少存在一个分支仅一边与u 相连,显然这边是G 的割边 ,故(G),所以 (G)=K(G) uG。,如图)(1)(,32)(,5GGpGpG名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 7 页 - - - - - - - - - () 设 K(G)=2, 且v1,v2 为 G 的一个顶点割。 G1=G-v1 连通,则 v2 是 G1 的割点且 v2 在 G1 中的度小于等于, 类似于 (2)知在 G1 中存在一割边e2(关联 v2)使得 G1-e2不连通另一方面由
6、于(G)=K(G)=2 故 G-e2 连通由于G1-e2= (G-e2)-v1,故 v1 是G-e2 的割点,且 v1 在 G-e2 中的度小于等于,于是类似于(2)知,在 G-e2 中存在一割边 e1,即(G-e2)-e1=G-e1,e2 不连通,故 (G)=2.所以 (G)=K(G). () 设 k(G) =3,于是,有 3 =k(G) (G)=3 ,知8证明:一个图G是2边连通的当且仅当G的任意两个顶点由至少两条边不重的通路所连通 . 分析:这个题的证明关键是理解2边连通的定义。证明: (必要性)因为G 是2边连通的,所以G 没有割边。设u,v 是 G 中任意两个顶点,由 G 的连通性知
7、u,v 之间存在一条路径P1,若还存在从u 到 v 的与 P1 边不重的路径 P2,设 C=P1P2,则 C 中含 u,v 的回路,若从u 到 v 的任意另外路径和P1 都有一条(或几条) 公共边,也就是存在边e 在从 u 到 v 的任何路径中, 则从 G 中删除 e,G 就不连通了,于是e成了 G 中一割边,矛盾。(充分性)假设G 不是一个 2-边连通的,则G 中有割边,设e=(u,v)为 G 中一割边,由已知条件可知, u 与 v 处于同一简单回路C 中,于是 e处在 C 中,因而从 G 中删除 e后 G 仍然连通,这与G 中无割边矛盾。9 举例说明:若在2连通图G中, P是一条,u通路,
8、 则G不一定包含一条与P内部不相交的,u通路Q。解 如右图 G,易知 G 是 2连通的,若取 P 为 uv1v2v,则 G 中不存在 Q 了。10证明:若G中无长度为偶数的回路, 则G的每个块或者是2K, 或者是长度为奇数的回路 . 分析:块是G 的一个连通的极大不可分子图,按照不可分图的定义,有G 的每个块应该是没有割点的。因此,如果能证明G 的某个块如果既不是2K,也不是长度为奇数的回路,再由已知条件G 中无长度为偶数的回路,则可得出G 的这个块肯定存在割点,则可导出矛盾。本题使用反证法。证明:设 K 是 G 的一个块,若k 既不是K2 也不是奇回路,则k 至少有三个顶点,且存在割边 e=
9、uv,于是 u,v 中必有一个是割点,此与k 是块相矛盾。11证明:不是块的连通图G至少有两个块 , 其中每个块恰含一个割点. )(G3)(GG)(v V1 V2 u G 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 7 页 - - - - - - - - - 分析:一个图不是块,按照块的定义,这个图肯定含有割点v,对图分块的时候也应该以割点为标准进行,而且分得的块中必定含这个割点,否则所得到的子图一定不是极大不可分子图,从而不会是一个块。证明:由块的定义知,若图G 不
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 2022年离散数学刘任任版 2022 刘任任版
限制150内