《2022年《离散数学》刘任任版 .pdf》由会员分享，可在线阅读，更多相关《2022年《离散数学》刘任任版 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 不
10、是块且连通，则G 有割点，依次在有割点的地方将G分解成块，一个割点可分成两块，每个块中含G 中的一个割点。如下图G。易知 u,v 是割点， G 可分成四个块K1 K4 。其中每个块恰含一个割点。12证明：图G中块的数目等于GVbG1其中 , b表示包含的块的数目 . 分析：一个图 G 的非割点只能分布在G 的一个块中， 即b=1 （当 v 是 G 的非割点时），且每个块至少包含一个割点。因此下面就从G 的割点入手进行证明。证明中使用了归纳法。证明：先考虑G 是连通的情况（1G） ，对 G 中的割点数n 用归纳法。由于对 G 的非割点v，b(v)=1，即 b(v)-1 =0，故对 n=0 时，G
11、 的块数为 1GVb1结论成立。假设 G 中的割点数nk（k0）时，结论成立。对 n=k+1 的情况，任取G 的一个割点a，可将 G 分解为连通子图Gi，使得 a 在 Gi中不是割点， a 又是 Gi的公共点。这样，每一个Gi，有且仅有一个块含有a，若这些 Gi共有r 个，则 b(a)=r，又显然 Gi的块也是 G 的块，且 Gi的割点数ilk。故由归纳法假设Gi的块的块数为1),2, 1(1ribiGVi，这里)(vbi是 Gi中含 v 的块的块数，注意到Gi中异于 a的 v，b(v)= )(vbi，而 a在每一个 Gi中均为非割点，故),2 , 1)(riabi。于是 Gi的块数为 1),
12、 2, 1(1ribavGVi将所有 Gi的块全部加起来，则得到G 的块数为：ravGVrib11=ravGVb1=1+(r-1) avGVb1=1GVb1由归纳法可知，当G 连通时，结论成立。当 G 不连通时，对每个连通分支上述结论显然成立。uvG1k3vuvuvv4k3k2k名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 因此有图G中块的数目等于GVbG113给出一个求图的块的好算法。分析：设 G 是一个具有p 个顶点， q
13、 条边， w 个连通分支的图。求图G 的块可先求图G的任一生成森林F，且对每一边eF，求 F+e 中的唯一回路，设这些回路C1，C2，Cq-p+w都已求得，（这些都有好算法） 。在此基础上，我们注意到，两个回路（或一个回路与一个块）若有多于1个公共点，则它们属于同一块。此外，由割边的定义知，G 的任一割边不含于任何回路中，且它们都是G 的块。基于这些道理，可得如下求图G 的块的好算法。解：求图的块的算法：（1）令 s=1，t=1，n=q-p+w （2）若 n0，输入 C1，C2， Cn；否则，转第4 步。（3）若，令tsstssCCVCVCC1|)()(|s且对 i=s+t， n-1，令1CC
14、1inni，转第 4 步；否则， t=t+1，转第 5 步。（4）若 sn，令 t=1，转第 3 步；否则，算法停止 （这时 C1，C2，Cn与E（G）- C1 ，C2， Cn 中的每一边都是G 的块）（5）若 s+tn 转第 3 步；否则， s=s+1，转第 4 步。本算法除了求回路有已知的好算法外，计算量主要在第3 步，比较tssCC与的顶点寻找它们的公共点的运算中，这些运算不超出p2*(q-p+w) 次，故是好算法。14证明：prH, 12是12r连通的。分析：只要证明prH, 12不存在少于12r个顶点的顶点割集。 设V是一个12| |rV的任一顶点子集，可分rV2| |和rV2| |
15、两种情形证明。证明：(1) 当rV2| |时，根据定理7.3.1 的证明，V不是prH,2的顶点割集，当然更不是在prH,2上加些边的prH,12的顶点割集。(2) 当rV2| |时，设V是prH,12的顶点割集，ji,属于, 12VHpr的不同分支。考察顶点集合, 1,.,1,jjiiS和,1,.,1,iijjT这里加法取模n名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 若S或T中有一个含V的顶点少于r个，则在,12VHpr
16、中存在从i到j的路。与V为顶点割集矛盾。若S和T中都有V的r个顶点，则：若S或T中，有一个 (不妨说S)中V的r个顶点不是相继连成段，则VS中存在从i到j的路。与V为顶点割集矛盾。若S与T中，V的r个顶点都是相继连成一段的。若S与T中至少有一个没有被分成两段，则立即与V为顶点割集矛盾；若VS被分成两段：含i的记1S，含j的记2S，且VT也被分为两段：含i的记1T，含j的记2T。这样，VV被分为两段：含i的11TS和含j的22TS。这两段都是连通的，且含i段的中间点 (或最靠近中间的一点 )0i与含j段的类似点0j满足：)(21)(2000为奇数为偶数nninnij故0i与0j有边相连，在, 1
17、2VHpr中有路 (jjii,.,.,00)，与V为顶点割集矛盾。综上所述，prH,12是12r连通的。15证明：mHHnmnm,. 分析：根据定理7.3.1，图nmH,是 m-连通图，因此有又根据nmH,的构造，可知，再由定理7.1.1 可证。证明：由定理7.3.1 知：已知： k 16试画出8. 4H、8.5H和9. 5H分析：根据书上第54 页构造nmH,的方法可构造出8. 4H、8 .5H和9 .5H。(i)8. 4H: r = 2 ,p=8, 对任意i,j V(8.4H), i- j r 或者mHnm）（,.,mkmmHnm因此）（而.,mHnm）（故).(mod),(mod,pjj
18、piirji其中，mHnm）（,mHnm）（,名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 则8 . 4H如下图：(ii) 8. 5H图：r =2,p=8,则在8.4H中添加连接顶点i 与 i+p/2(mod p)的边， 其中 1ip/2, 15; 2 6; 3 7; 4 0. 则8 . 5H图如下：(iii) 9.5H图: r=2,在9,.4H图上添加连接顶点0 与（p-1）/2 和(p+1）/2 的边，以及顶点i 与i +（p+1）/2(mod p) 的边，其中 1i （p-1）/2. 04; 0 5; 1 6; 2 7; 38. 则9. 5H图如下：6, 7, 86 ,7,0jiji7,97, 1jiji7, 8,97, 8,0jiji8,108, 1jiji07432156图9,5H807432156图8,5H07432156图8,4H名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -