2024年1月7日发(作者：邢台三模数学试卷答案解析)

习题七

1．对图7.7中的两个图，各作出两个顶点割。

（a）

图7.7

（b）

解： 对图7.7增加加节点标记如下图所示，

则(a)的两个顶点割为： V11={a,b} ； V12={c,d}

(b)的两个顶点割为： V21={u,v} ； V12={y}

yacwduvxb(a)图7.7(b)

2．求图7.7中两个图的G和G.

3．试作出一个连通图G, 使之满足：GGG

解：如上两个图，有 k(G1)=λ(G1)=2, k(G2)=1, λ(G2)=2

k解：做连通图G如下，于是有 ：

(G)(G)(G)

4．求证, 若Gp,q是k边连通的, 则qkp/2.

证明：设G是k—边连通的，由定义有λ(G)≧k. 又由定理7.1.2知λ(G)≦

p

，因此有 k≦λ(G) ≦

2

q

 ≦

2qpp

q ，从而

q

 即 k≦

2

kp

。

2qp2

5．求证, 若G是p阶简单图, 且Gp2, 则GG.

分析：由G是简单图，且Gp2，可知G中的δ(G)只能等于 p-1或p-2；

如δ(G)= p-1,则G是一个完全图，根据书中规定，有k(G)=p-1=δ(G)；

如δ(G)= p-2,则从G中任取V（G）的子集V1，其中|V1|=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，GG，有k(G)=k-2。

证明：因为G是简单图 ,所以d(v)≦p-1,v∈V(G),已知δ(G)≧p-2

（ⅰ）若δ(G)= p-1,则G=Kp（完全图），故k(G)=p-1=δ(G)。

（ⅱ）若δ(G)= p-2, 则 G≠Kp,设u,v不邻接，但对任意的w∈V(G),有

uw,vw ∈E(G).于是，对任意的V1V(G),

| V1|=p-3 ,G-V1必连通.

因此必有k(G) ≧p-2=δ(G),但k(G) ≦δ(G)。

故k(G) =δ(G)。

6．找出一个p阶简单图, 使Gp3, 但GG.

解：如图

G，p5,(G)2p3,(G)1(G)。uG

7．设G为3正则简单图, 求证GG.

分析：G是一个3正则简单图，所以δ(G)=3，根据定理7.1.1有GG(G)，所以G只能等于0，1，2，3这四种情况。下面的证明中分别讨论了这四种情况下

G和G的关系。

证明：(1)若G=0，则G不连通,所以λ(G)=K(G).

(2) 设 K(G)=1,且u 是G中的一个割点，G-u不连通,由于d(u)=3,从而至少存在一个分支仅一边与u相连,显然这边是G的割边,故λ(G)＝１，所以λ(G)=K(G)

(３) 设K(G)=2,且{v1,v2}为G的一个顶点割。G1=G-v1连通,则v2是G1的割点且v2在G1中的度小于等于３，类似于(2)知在G1中存在一割边e2(关联v2)使得G1-e2不连通．另一方面由于λ(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

) ≦δ(G)=3 ,知

（G）(G)3

8．证明：一个图G是2边连通的当且仅当G的任意两个顶点由至少两条边不重的通路所连通.

分析：这个题的证明关键是理解2边连通的定义。

证明：（必要性）因为G是2边连通的，所以G没有割边。设u，v是G中任意两个顶点，由G的连通性知u，v之间存在一条路径P1，若还存在从u到v的与P1边不重的路径P2，设C=P1∪P2，则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,通路, 则G不一定包含一条与P内部不相交的u,通路Q。

解 如右图G，易知G是2—连通的，

若取P为uv1v2v，

则G中不存在Q了。

G

V1

u

V2

v

10．证明：若G中无长度为偶数的回路, 则G的每个块或者是K2, 或者是长度为奇数的回路.

分析：块是G的一个连通的极大不可分子图，按照不可分图的定义，有G的每个块应该是没有割点的。因此，如果能证明G的某个块如果既不是K2，也不是长度为奇数的回路，再由已知条件G中无长度为偶数的回路，则可得出G的这个块肯定存在割点，则可导出矛盾。本题使用反证法。

证明： 设K是G的一个块，若k既不是 K2也不是奇回路，则k至少有三个顶点，且存在割边e=uv,于是u,v中必有一个是割点，此与k是块相矛盾。

11．证明：不是块的连通图G至少有两个块, 其中每个块恰含一个割点.

分析：一个图不是块，按照块的定义，这个图肯定含有割点v，对图分块的时候也应该以割点为标准进行，而且分得的块中必定含这个割点，否则所得到的子图一定不是极大不可分子图，从而不会是一个块。

证明：由块的定义知，若图G不是块且连通，则G有割点，依次在有割点的地方将G分解成块，一个割点可分成两块，每个块中含G中的一个割点。如下图G。

易知 u,v是割点，G可分成四个块K1 ～K4 。其中每个块恰含一个割点。

k3vuvuk2v3Guvvk1k4

12．证明：图G中块的数目等于

Gb1 其中,

b表示包含的块的数目.

VG分析：一个图G的非割点只能分布在G的一个块中，即b=1（当v是G的非割点时），且每个块至少包含一个割点。因此下面就从G的割点入手进行证明。证明中使用了归纳法。

证明：先考虑G是连通的情况（G1），对G中的割点数n用归纳法。

由于对G的非割点v，b(v)=1，即b(v)-1 =0，故对n=0时，G的块数为1b1结VG论成立。

假设G中的割点数n≤k（k≥0）时，结论成立。

对n=k+1的情况，任取G的一个割点a，可将G分解为连通子图Gi，使得a在Gi中不是割点，a又是Gi的公共点。这样，每一个Gi，有且仅有一个块含有a，若这些Gi共有r个，则b(a)=r，又显然Gi的块也是G的块，且Gi的割点数li≤k。故由归纳法假设Gi的块的块数为1b1(i1,2,,r)，这里b(v)是G中含v的块的块数，注意到iiiVGiGi中异于a的v，b(v)=

bi(v)，而a在每一个Gi中均为非割点，故bi(a)(i1,2,,r)。于是Gi的块数为1b1(i1,2,,r)

VGiva将所有Gi的块全部加起来，则得到G的块数为：

rb1=rb1=1+(r-1)

b1=1b1

i1VGvarVGvaVGvaVG由归纳法可知，当G连通时，结论成立。

当G不连通时，对每个连通分支上述结论显然成立。

因此有图G中块的数目等于

Gb1

VG

13． 给出一个求图的块的好算法。

分析：设G是一个具有p个顶点，q条边，w个连通分支的图。求图G的块可先求图G的任一生成森林F，且对每一边eF，求F+e中的唯一回路，设这些回路C1，C2，…，Cq-p+w都已求得，（这些都有好算法）。在此基础上，我们注意到，两个回路（或一个回路与一个块）若有多于1个公共点，则它们属于同一块。此外，由割边的定义知，G的任一割边不含于任何回路中，且它们都是G的块。基于这些道理，可得如下求图G的块的好算法。

解：

求图的块的算法：

（1）令s=1，t=1，n=q-p+w

（2）若n>0，输入C1，C2，…，Cn；否则，转第4步。

（3）若|V(Cs)V(Cst)|1且对i=s+t，…，n-1，令，令CsCsCst，CiCi1，nn1，转第4步；否则，t=t+1，转第5步。

（4）若s

（5）若s+t≤n转第3步；否则，s=s+1，转第4步。

本算法除了求回路有已知的好算法外，计算量主要在第3步，比较Cs与Cst的顶点寻找它们的公共点的运算中，这些运算不超出p2*(q-p+w)次，故是好算法。

14．证明：H2r1,p是2r1连通的。

分析：只要证明H2r1,p不存在少于2r1个顶点的顶点割集。设V\'是一个|V\'|2r1的任一顶点子集，可分|V\'|2r和|V\'|2r两种情形证明。

证明：

(1) 当|V\'|2r时，根据定理7.3.1的证明，V\'不是H2r,p的顶点割集，当然更不是在H2r,p上加些边的H2r1,p的顶点割集。

(2) 当|V\'|2r时，设V\'是H2r1,p的顶点割集，i,j属于H2r1,pV\'的不同分支。考察顶点集合

S{i,i1,...,j1,j}

和

T{j,j1,...,i1,i} 这里加法取模n

若S或T中有一个含V\'的顶点少于r个，则在H2r1,pV\'中存在从i到j的路。与V\'为顶点割集矛盾。

若S和T中都有V\'的r个顶点，则：

 若S或T中，有一个(不妨说S)中V\'的r个顶点不是相继连成段，则SV\'中存在从i到j的路。与V\'为顶点割集矛盾。

 若S与T中，V\'的r个顶点都是相继连成一段的。若S与T中至少有一个没有被分成两段，则立即与V\'为顶点割集矛盾；若SV\'被分成两段：含i的记S1，含j的记S2，且TV\'也被分为两段：含i的记T1，含j的记T2。这样，VV\'被分为两段：含i的S1T1 和含j的S2T2。这两段都是连通的，且含i段的中间点(或最靠近中间的一点)i0与含j段的类似点j0满足：

ni02j0n1i02(n为偶数)

(n为奇数)故i0与j0有边相连，在H2r1,pV\'中有路(i,...,i0,j0,...,j)，与V\'为顶点割集矛盾。

综上所述，H2r1,p是2r1连通的。

15．证明：Hm,nHm,nm.



（分析：根据定理7.3.1，图Hm,n是m-连通图，因此有

H

m

,n

）

m

又根据Hm,n的构造，可知

（

H

m

,n

）

m ，再由定理7.1.1可证。

证明：由定理7.3.1知：

（

H

m

,n

）

m

已知：k≦λ ≦δ

而（Hm,n）m.因此mkm.

故（Hm,n）m.16．试画出H4.8、H5.8和H5.9

分析：根据书上第54页构造Hm,n的方法可构造出H4.8、H5.8和H5.9。

(i)

H4.8: r = 2 ,p=8,对任意 i,j ∈V(H4.8), ︱i- j︱≤r 或者

ijr,其中，ii(modp),jj(modp).

i0,j7,6i8,j7,6i1,j7i9,j76071则H4.8如下图：

254H4,8图3(ii)

H5.8图：r =2,p=8,则在H4.8中添加连接顶点i 与 i+p/2(mod p)的边，其中1≤i≤p/2,

∴1→5; 2 →6; 3 →7; 4 →0. 则H5.8图如下

071654(iii)

H5.9图:

23H5,8图：

r=2,在H4,.9图上添加连接顶点0与（p-1）/2和(p+1）/2的边，以及顶点 i 与

i +（p+1）/2(mod p) 的边，其中1≤ i< （p-1）/2.

i9,j8,7i10,j8

∴0→4; 0 →5; 1 →6; 2 →7; 3→8.

则H5.9图如下：

78i0,j8,7i1,j801654H5,9图23


更多推荐

顶点,证明,回路,等于,割点,不可,求图