2024年1月7日发(作者：南通市初三二模数学试卷)

习 题 九

1．证明：任何树最多只有一个完美匹配

分析：树是连通没有回路的图；树的完美匹配是树存在一个匹配M，满足树的所有顶点v都是M-饱和点。而两个完美匹配中不同的边所关联的顶点的度至少为2，否则如果等于1的话，则该顶点关联的边只有一条，在构造完美匹配的时候为了使得这个点成饱和点，只有一种选择。

证明：设树T有两个或两个以上的完美匹配，任取完美匹配M1和M2，M1M2。于是易知边导出子图HT[M1M2]中的每个顶点v满足dH(v)2。于是HM1M2。中存在回路，从而T中有回路。此与T是树矛盾，故结论成立。

2．证明：树G有完美匹配当且仅当对任意vV(G)，均有O(Gv)1

分析：一方面，由定理9.1.3 图G存在完美匹配当且仅当对任意SV(G)，有O(GS)|S|，所以如果树G有完美匹配，则O(Gv)|{v}|1；而G有完美匹配，说明|V(G)|偶数，所以O(Gv)1；从而有O(Gv)1。

另一方面，如果对任意vV(G)，均有O(Gv)1，则对v而言，可利用这个这个奇分支找到v关联的唯一边，从而构造出G的一个完美匹配。

证明：必要性 设G有完美匹配。

由定理9.1.3，取S{v}，则

O(Gv)O(GS)|S|1

又 ∵G有完美匹配，∴|V(G)|偶数。于是|V(Gv)|=奇数。

故

O(Gv)1. 从而

O(Gv)1.

充分性 设对任意vV(G)，有O(Gv)1.

即Gv恰有一个奇分支C0(v)，因G是树，故v只能与C0(v)中的一个顶点邻接。设v与C0(v)的关联边为e(v)vuE(G)。显然v确定以后，uv是唯一确定的，且易知C0(u)uv。因为G-v只有一个奇分支C0(v)，则G-u以后，v应该与G-v的其他偶分支在一个连通分支中，而这个分支的顶点数显然是奇数，从而构成G-u的唯一一个奇分支C0(u)，而u与这个奇分支中的顶点显V(G)，按这样的方法构造其关联边e(v)，然也只有与v邻接，所以C0(u)uv。于是对任意v所的的匹配

M{e(v)|vV(G)}就是G的一个完美匹配

3．设k1是奇数。举出没有完美匹配的k-正则简单图的例子。

分析：作G如下：取2k-1个顶点v1,v2,,v2k1，在奇足标顶点和偶足标顶点间两两连以边外，

再连以v1v3,v5v7,,v2k5v2k3边，所得图记为G0，显然G0除v2k1外其余顶点的度均为k，而v2k1的度为k-1，取k个两两不相交的G0的拷贝和一个新顶点v0，并把每个G0拷贝中对应于v2k1的顶点与v0相连以边。最后所得的图记为G，显然G是k-正则的简单图。又由于G0含2k-1个顶点，则G的顶点数为：k*(2k-1)+1。所以如果G有一个完美匹配M的话，则

|M|=假设M是G的一个完美匹配，则其边应来自k个独立的G0，和跟v0相关联的一条边。

而每个G0，其包含的顶点数为2k-1，所以G0能提供给M的边最多为k-1条，k个这样的G0能提供给M的边最多为k*(k-1)，因此M最多包含的边为k*(k-1)+1=k2-(k-1)<

k能有完美匹配。

解：令k=3，得到的图G0及G如下：

V0

2k*(2k1)12k1=k。

22k1，因此G不可2V1

V2

V5

V3

V4

V5

V1

V2

V5

V3

V4

V1

V2

V3

V4

4．设k0为偶数，举出没有完美匹配的k-正则简单图的例子.

分析：当k为偶数时，取G=Kk+1，则G的顶点数为k+1，显然G的顶点数为奇数，所以G无完美匹配。

解：令k=2时，可构造出无完美匹配的2-正则图K3。

5．两人在图G上进行对奕双方分别执黑子和白子，轮流向G的不同顶点v0,v1,v2,下子，要

求当i >0时，vi与vi1邻接，并规定最后可下子的一方获胜。若规定执黑子者先下子，试证明执黑子的一方有取胜的策略当且仅当G无完美匹配。

分析：假设G有完美匹配，则G的每个顶点都是M-饱和点，这样先下者无论取哪个顶点，后下者都可取其相邻的M-饱和点，这样先下的人必输；因此先下的人如要赢的话，G中肯定无完美匹配。

反过来，如果G中无完美匹配，由于任何图都有最大匹配，则可找到G的一个最大匹配M，由于M不是完美匹配，因此G中存在M-非饱和点v，先下的黑方就可找到这个点下，则与v相邻的下一个点必是M-饱和点，不然，M∪{uv}就是一个更大的匹配，与M是最大匹配矛盾。同理G中不存在M可增广路，故黑方所选vi必是M饱和点，如此下去，最后必是白方无子可下，故黑方必胜。

证明：必要性（反证法） 若G中存在一个完美匹配M，则G中任何点v都是M饱和点。故不论执黑子（先下者）一方如何取vi1，白方总可以取M中和vi1关联边的另一端点作为vi，于是，黑方必输。

充分性. 设G中不存在完美匹配，令M是G的最大匹配，而v0是非M饱和点。于是，黑方可先取v0点，白方所选v1必是M饱和点（因M是最大的匹配）由M的最大性可知G中不存在M可增广路，故黑方所选vi必是M饱和点，如此下去，最后必是白方无子可下，故黑方必胜。

6．证明：二分图G有完美匹配当且仅当对任何Sv(G)，有

|S|NG(S) 成立

举例说明若G不是二分图，则上述条件未必充分。

分析：由定理9.1.2Hall定理，对于具有二划分（X,Y）的二分图，G有饱和X中每个顶点的匹配当且仅当对任意的SX,有|S|NG(S)，显然如果G有完美匹配M的话，则M既饱和X，也饱和Y。但当G不是二分图时，这个结论不一定成立，如K2n+1对任意的SV(G)满足|S||NG(S)|，但它无完美匹配。

证明：必要性. 设G有完美匹配M，则M饱和X及Y，由Hall定理和对任何SX或SY，有

|S||NG(S)|

今任取SV(G)，有SS1S2,S1X,S2Y于是有

|S||S1S2||S1||S2||NG(S1)||NG(S2)|

|NG(S1S2)||NG(S)|

充分性：设对任何SV(G)，有|S||NG(S)|.

即任取SX，有|S|NG(S)|，于是由Hall定理，存在饱和X的匹配M(X)，同理，存在饱和Y的匹配M(Y)，从而|X||Y|，易知M(X)和M(Y)都是完美匹配。

当G不是二分图时，条件不充分，如GK3。

7．2n个学生做化学实验，每两个人一组，如果每对学生只在一起互作一次实验，试作出一个安排，使任意两个学生都在一起做过实验。

分析：该题可转化为对具有2n个顶点（可分别记为0，1，2，…，2n-1）的完全图构造其不同的2n-1个完美匹配，使得（0，1）（0，2）…（0，2n-1），（1，2）（1，3），…，（1，2n-1）…，

（2n-2,2n-1）在这2n-1个匹配中出现且仅出现一次。

解： 共安排2n-1次实验，可使任意两个学生都在一起做过实验。安排如下：

第1次：(0, 1), (2, 2n-1), (3, 2n-2), …… , (x, y)。 其中， x+y=2n+1;

第2次：(0, 2), (3, 1), (4, 2n-1), ……, (x, y) 。 其中， x+y=2n+3;

………

第2n-1次：(0, 2n-1), (1, 2n-2), (2, 2n-3), ……, (x, y) 。 其中， x+y=2n-1;

8．试证明：任何一个（0,1）矩阵中，包含元素1的行或列的最小数目，等于位于不同行不同列的1的最大数目。

分析：由定理9.2.2，对二分图G，均成立(G)(G)（其中(G)为G的最大匹配数，(G)为G的点覆盖数）。将给定的（0，1）矩阵表示成一个二分图G(V1,V2,E)

V1{u1,,un}，V2{v1,,vn}.其中M(i,j)1当且仅当(ui,vj)E(G)

该题转化为了判断G的(G)和(G)的关系。

证明： 设Mmn是一个（0,1）矩阵.将Mmn表示成一个二分图G(V1,V2,E)，V1{u1,,un}，V2{v1,,vn}.其中

M(i,j)1当且仅当(ui,vj)E(G)

于是，G的（最小）点覆盖数(G)等于含Mmn中元素1的行（第i行元素1的数目表示顶点ui覆盖的边之数目）或列（第j列元素1的数目表示顶点vj覆盖的边数目）的数目。而G的最大匹配数(G)等于Mmn中位于不同行不同列的1的最大数目.

由定理9.2.2知，若G为二分图，则(G)(G)。故结论成立.

9．能否用5个12的长方表将图9-13中的10个11正方形完全遮盖住？

图9-13

分析：按如下方法作出G图：在图9-13的每个正方形格子中放一个顶点，u与v邻接当且仅当u与v所在的方格有公共边。则该问题等价于判断相应图G是否有完美匹配，

解：按照分析，构造图G如下：则有O(G{u})31|{u}|，由定理9.1.3可判断它没有完美匹配。因此不能用5个12的长方表将图9-13中的10个11正方形完全遮盖住。

10．试证明：G是二分图当且仅当对G的每个子图H均有(H)u

1|V(H)|。

2分析：若G=（X，Y）是二分图，显然X和Y都构成G的点独立集，所以G的最大独立数(G)|X|，

且(G)|Y|；而二分图的每个子图显然也是二分图。

证明：必要性.设G是二分图，于是G的任何子图H也是二分图，设H(X,Y)，|X||Y||V(H)|。不妨设|X||Y|。显然

(H)|X|， 因此，

2(H)2X|X||Y||V(H)|。于是，(H)1|V(H)|。

2充分性. 若G不是二分图，则G中含奇回路C。令HC。显然，

(H)V(H)/21|V(H)|。 矛盾。故G是二分图。

2

11．试证明：G是二分图当且仅当对G的每个适合(H)0的子图H，均有(H)(H).

分析：(G)是指G的最大独立集，(G)是指G的边覆盖数。

如果G是不含孤立点的二分图（X，Y），显然(G)=max(|X|,|Y|)，因此如果能证明(H)=max(|X|,|Y|)，则对不含孤立点的二分图G，有(G)(G)

证明： 必要性. 设G是二分图。

HG，(H)0，即H无孤立点。显然H也是二分图，设H(X,Y)，且|X||Y|。于是，(H)|X|。而一条边最多覆盖一个顶点，故(H)|X|。但由于H无孤立点，因此，(H)X，故(H)|X|(H)。

充分性. 若G不是二分图，则G含奇回路CH。设|V(H)|2n1,n1。于是

(H)n，而(H)n1(H)。矛盾。故G必为二分图。

12．设G是具有划分（X，Y）的二分图。证明：若对于任何uX,vY.均有d(u)d(v)，则G有饱和X中每一顶点的匹配。

分析：根据定理9.1.2，二分图G有饱和X中每个点的匹配当且仅当对任何SX，有|S||NG(S)|根据这个结论，如果能说明满足条件的二分图G中不存在任何SX，有|S||NG(S)|，则题目得证。

证明： 由题意知，对uX,d(u)1。

若G中不存在饱和X的匹配，则由Hall定理，存在SX，使|S||NG(S)|。

设S{u1,,um}，NG(S){vj1,,vjn}，其中mn。

由对任何uX,vY，d(u)d(v)，得都是NG(S)的点关联的边，因此d(u)uS因此在NG(S)中总存在一点，有d(vjr)d(ut)。矛盾。故G中存在饱和X的匹配。

13．证明（Hall定理的推广）：在以G(X,Y)为二划分的二分图G中，最大匹配数(G)为

vNG(S)d(u)d(v)，但由于S中的点关联的边d(v)，因此有d(u)d(v)，但mn，uSvNG(S)uSvNG(S)(G)min{|XS||NG(S)|}

sx分析：由定理9.2.2有：如果一个图G是二分图，则(G)(G)，(G)是G的最大匹配数，(G)是G的最小覆盖。因此如果能说明min{|XS||NG(S)|}等于(G)的话，则本题得以证明。

sx| 证明：由于{XS}NG(S)，所以|XS||NG(S)|=|{XS}{NG(S)}显然{XS}{NG而G的任意一个覆盖都可以写成{XS}{NG(S)}是G的一个覆盖，(S)}的min{|XS||N(S)|}

因此有(G)(G)=min{|XS||N(S)|}

形式，所以(G)=GsxGsx

14．证明：在无孤立点的二分图G中，最大独立集的顶点集α(G)等于最小边覆盖数\'(H)。

证明：参见题11

15．在9个人的人群中，假设有一个人认识另外两个人，有两个人每人认识另外4个人，有4个人认识另外5个人，余下的两个人每人认识另外的6个人。证明：有3个人，他们全部互相认识。

分析：将该题中的人用图中的节点表示，两个节点有连线当且仅当两个人认识，则该题转化为求证满足上述条件的图G含有一个K3。

要判断一个图是否含有K3，我们先要了解以下概念和定理：

T2，p：具有p个顶点的完全2分图，如果p是偶数，则该图的每一部分顶点数为p/2；如果p为奇数，则该图的其中一部分顶点数为(p-1)/2，另一部分顶点数为(p+1)/2。

Turan定理（托兰定理）的推论：若简单图G不含K3，则E(G)≤E(T2,p)，且当E(G)=E(T2,p)时，有GT2,p

该定理的严格内容为：若简单图G不含Km+1，则E(G)≤E(Tm，p)，且当E(G)=E(Tm，p)时，有GTm,p其中Tm，p为具有p个顶点的完全m部图。这里我们令m=2，只说明我们所要的结论。

这个定理的证明请参看Bondy和Murty著的《Graph Theory with Applications》中的定理7.9及其证明。

按照这个定理，我们只需判断E（G）>E(T2，9)=20即可。

证明：

方法一：由题意，可作一个9个点的图G，各顶点度序列为(6,6,5,5,5,4,4,2)。于是有

191qd(vi)(665555442)21> E(T2，9)=4*5=20

2i12由托兰定理推论有G含有一个K3，所以9人中的至少有三个相互认识。

方法二（反证法）假设9人中的任意三个都互不认识。由题意，设d(v0)6，如图，于是，v1~v6中的任何两顶点互不邻接，从而d(vi)3,

16．设G（p,q）是简单图，且qp/4，则G中包含三角形，请证明此结论。

分析：该题也可利用托兰定理的推论，如果能证明q>E（T2，p），则可判断G中包含三角形。

证明：当p为偶数时，E（T2，p）=22i1,,6。因此，只有d(u7)3或d(u8)3以及d(u0)3。但由题设，至少有8人认识3个以上的人，此与题意不符。

由已知条件E（G）=qp/4= E（T2，p）

pp=p2/4

22

p1p1p21 当p为奇数时，E（T2，p）==

2224p1由已知条件E（G）=qp2/4>=E（T2，p）

42由以上分析可知，当qp/4时，有E（G）> E（T2，p），所以G中包含三角形。

17．试找出一个简单图G(p,q)，使得qp2/4，但G不包含三角形。

p2分析：由于T2，p不包含三角形，且当p为偶数时，qp2/4

42p1p2/4所以任意的T2，p都是满足题目条件的不包含三角形的图。 当p为奇数时，q4解：取p=4，则T2，4右图所示。

18．将K13的边着红色或兰色，使其中既无三边红色的K3，也无10条边全着兰色的K5。

分析：如教材P115图9-11，将图中不邻接的两顶点之间用兰色的边联结，将邻接的两顶点之间的边着成红色，即满足题要求。

解：着色结果如下图。

19．设mmin{k,l}，求证r(k,l)2m/2

分析：显然，如果定mmin{k,l}，r(k,l)是指包含k团或l独立集的顶点数最少的图的顶点数。r(k,l)r(m,m)的由定理9.3.3当m≥2时，r(m,m)2m/2。

证明 ∵

r(k,l)r(m,m)2m/2

∴

r(k,l)2m/2,

mmin{k,l}

20．证明：当k3时，r(k,k)k2k22

k22，如果能证明分析：此结论的证明可仿照定理9.3.3的方法令pk2Yp中只有不到半数的图含有k团，同时Yp中也只有不到半数的图含有k独立集。于是Yp中必存在某个图它既不含有k团，也不含k独立集，由于这个结论对任意pk2k22的图都成立，因此有:

r(k,k)k2k22

证明：在定理9.3.3的证明中，取pk2k22.于是，有

|Y|p2|Yp|k/k!，则

kpk2pk2k!k2kk23k/2

k!令rkk2k3k/2rk23/223/22.828k3/21

21rk1k1e2.718(1)kk11又r3，故对于一切k3，lk，于是，

22|Ypk||Yp|1

2k22k仿定理9.3.3之证明，即得r(k,k)k2

21．在匈牙利算法的第3步中，假如y是非M—饱和的，如何得到一条从u到y的M—可增广路？

分析： 由二分图的定义及增广路径的定义，可知二分图中的增广路径具有如下性质：

(1) 起点和终点都是非M-饱和点，而其它所有点都是M-饱和点。

(2) 整条路径上没有重复的点。

(3)路径上总共有奇数条边，且所有第奇数条边都不在M中，所有第偶数条边都在M中。

(4)把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了1个。

解：根据以上分析，可得到求从u到非M饱和点y的M—可增广路径的算法如下：

1．For i=0 to n

2. { pre(vi)=null

3． Succ(vi)=null }

4． d(u)=0,d(vi)=∞

//初始置每个顶点的前导和后继顶点为null，u与u的距离为0，其他点与u的距离为∞

5． S={u} //以u为初始顶点构造所有的M-交错路，直到顶点y在某条交错路上为止

4．While (y不属于S) {

5． 任取S中的顶点v，

6. if succ(v)=null

7． For 每个与v邻接的顶点w {

8． If （w是M-饱和点并且 pre(w)≠null）{d(w)=d(v)+1}

9. if （(d(w)是奇数并且vw不属于M)或者(d(w)是偶数并且vw属于M)

9． { succ(v)≠null，pre(w)=v，S=S∪{W} }

10． }

11． }//结束while循环找到了一条从u到y的M-可增广路

算法结束以后得到一条路径P=y→pre(y) →pre(pre(y)) →…→u

则P-即为一条从u到y的M-可增广路径。

22．说明在匈牙利算法的第3步中，执行M:ME(P) 后，所得到的M 仍是G 的一个匹配.

说明：因为P是一条M可增广路，所以ME(P)可以看作在P上，保留第奇数条边，去掉第偶数条得到的一个边集，显然P的所有偶数条边是没有公共顶点的，所以ME(P)仍是G的一个匹配。

23．在图9-12中，将边x3y4去掉，利用匈牙利算法求所得二分图的完美匹配，若不存在，则给出使|NG(S)|<|S|成立的S。

分析：按照匈牙利算法可得如下去掉边x3y4以后求其完美匹配的过程。

解：取初始匹配M={x1y2,x2y1,x3y3,x5y5}

(1)X中存在非饱和点,令S={x4},T=φ

(2)NG(S)={y2,y3}≠T ,取y2∈NG(S)-T

(3)y2是M-饱和点, x1y2∈M,令S={x1,x4}, T={y2}

（4） NG(S)={y2,y3}≠T, 取y3∈NG(S)-T

(5) y3是M-饱和点, x3y3∈M,令S={x1,x3,x4}, NG(S)={y2,y3}

有|NG(S)|=2<|S|=3 算法结束,图中没有完美匹配.

24．将匈牙利算法稍加修改，使之能用来求二分图中的最大匹配.

分析：注意到匈牙利算法在一个M-不饱和点u的交错树上出现|N（S）|<|S|时，根据Hall定理知不存在饱和X的匹配而停止。但当求其最大匹配时，应继续先判断X-S=φ是否成立？若不成立，再判断X-S还是否存在其他M-不饱和点？一直到所有不饱和点都找不到M-增广路时，才得到最大匹配。根据这一想法，可修改匈牙利算法以求二分图的最大匹配。

解：算法如下。

（1） 置S=φ，T=φ

（2） 若X-S已M-饱和，则停止；否则，设u是X-S中的一个M-不饱和点，置S=S∪{u}。

（3） 若N（S）=T，转（5），否则设y∈N(S)-T

（4） 若y是M-饱和的，设yz∈M,用S∪{z}代替S，T∪{y}代替T，转（3）；否则，(u,y)-交错路是M-增广路P，用M’=ME(P)代替M，转（1）。

（5） 若X-S=φ则停，否则，转（2）。


更多推荐

匹配,顶点,定理