二部图
定义：图G?(V,E)称为二部图(bipartite graph)，如果V是两个互不相交的集合V1,V2的开集，且V1和V2中的顶点互不相邻. 这样的二部图也常称为(V1,V2)-二部图.
定义：图G的匹配是由G中没有公共顶点构成的集合，与匹配M中的边关联的顶点称为是被M-浸润的(saturated by M)，其余的顶点称为未被M-浸润的(M-unsaturated). 图G的一个完美匹配(perfect matching)是浸润的所有顶点的匹配. 图G的边数最多的匹配称为一个最大匹配(maximum matching).
11111（a）图1（b）
例如在上图中，粗边给出了一个匹配M1，显然两条细边给出了一个最大匹配M2. 定义：设M是图G的一个匹配. 如果路径P的边交替出现在M和不出现在M中，则称P是一条M-交错路径(M-alternating path). 两个顶点都未被M-浸润的交错路径称为
M-增广路径(M-augmenting path).
在上例中存在M1-增广路径，M2是最大匹配，而不存在M2-增广路径，这不是偶然的. 因为可以让（留作习题）：图G的一个匹配M是最大匹配?G中无M-增广路径.
定义：图G的一个顶点覆盖(covering)是一些顶点构成的集合??V(G)，使得G的任何一边都有一个顶点含于?. 一个顶点覆盖?称为最小顶点覆盖，是指不存在覆盖?'，使得?'??.
设?是G的一个顶点覆盖，M是G的一个匹配，显然??M. 我们关心对于最大匹配的最小顶点覆盖来说，等式是否成立. 在图1(a)中，等式成立，而图1(b)中最小顶点覆盖大小为3，而最大匹配大小为2. 注意图1(a)为二部图，图1(b)为有5条边的圈，从而不是二部图（可以一个图G是二部图?G中不含奇数边的图，证明留作习题）.对于二部图，我们有下面一般的结论：
定理：设G是(X,Y)-二部图，则G的最大匹配的大小等于G的最小顶点覆盖的大小(k?nig 1931).
证明：设M是G的最大匹配，而Q是M的最小顶点覆盖，要证M?Q.
显然Q?M，故只需证明存在G的M个顶点的覆盖（则M?Q），对于M中每一条边，如果存在未被M-浸润的X中顶点出发的交错路径可达这条边，则选择此边在Y中的顶点；否则选择此边在X中的顶点，这样就选了M个顶点，记为U.
设xy?E，x?X,y?Y，只需证明x或y?U，或xy?M，则由U的定义得证.下证之：设xy?M. 又由M是最大匹配，故?x1y1?M（其中x1?X,y1?Y）且x?x1或，由于xy是M-交错路径，故y?U.下设x?x1，如果y?y1. 若y?y1（此时x?M）
则y1?U，由U的定义：某条交错路径可达y1. 则存在交错路径P'可达y；或Pyx?U，
（若x1?P）；或Py1x1y. 这样就出现了M-增广路径，与M是最大匹配矛盾，故x?U.
1y1x1=xy1 对于(X,Y)-二部图，若存在一个浸润X的匹配，则显然???X，至少在Y中存在?个顶点与?中的顶点相邻. 我们用N(?)表示与?中顶点相邻的顶点构成的集合，下面的定理说明“???X,N(?)??”这个显然的必要条件也是充分的
定理(1935)：(X,Y)-二部图中存在浸润X的匹配????X,N(?)??.
证明：“?”由k?nig定理，只需证明对每个顶点覆盖z，有z?X. 令s?X?z?X，则s的点都不在X中，因此
N(s)中的点都在z中（由顶点覆盖定义），故
z?z?X?N(s)?z?X?s?X，证毕.
X11111z?XY
1111
图的连通性
因为连通与否与图是否含环无关，故本小节假定所有图都不含环，且n(G)?1. 定义1：图G的一个点割(vertex cut)是一个集合S?V(G)，使得G?S的连通分量
多于一个G的连通度(connectivity)，?(G)是使得G?S不连通或只有一个顶点的顶点集合S大小的最小值. 如果G的连通度最少是?，则称G是?-连通的(κ-connected).
由定义，显然可知： ①连通图都是1-连通的； ②G是不连通的?G的连通度为0；
③顶点数大于2的图的连通度为1?它是连通的且有一个割点.
若图G的连通度为?，则?(G)??，故G中至少有??n?条边（见习题１）. 我们
?2????n关心是否可以给出n个顶点的?-连通图且有??条边（即下界是否可以取到）.习题１给
?2???出了肯定的回答.
定义2：图G中的边割(edge cut)是一顶点在S中，一顶点在V(G)?S中的G中所有边构成的集合，记为[S,S]（S?V(G)）. 若使得G?[S,S]不连通的[S,S]边数最小
值为?，则称G是?-边连通的，?称为G的边连通度，记为?'(G).
G是2-边连通的. 图在下图G中粗线标出的边割是G的最小边割，因此?'(G)?2，G中还标出了一个只含一个顶点的点割，故G是1-连通的.
S1111111S111111111 定理3(Whitney 1932)：设G是简单图，则?(G)??'(G)??(G).
证明：设d(v)?min{d(x):x?V(G)}，即d(v)??(G)，则与v关联的所有边构成一个边割，故?'(G)??(G)，下证?(G)??'(G).
显然?(G)?n(G)?1，设[S,S]为G的最小边割，若S中的顶点与S中的顶点都邻接，则[S,S]?SS?n(G)?1??(G)，命题得证.
下设存在x?S,y?S.则x,y不相邻，构造集合T：T包含S中x的相邻顶点；T包含S-{x}中的所有与S中顶点有相邻顶点的顶点（或T?{v?S:xv?V(E)}?{v?S?{x}：存在u?S使得vu??(E)}）. 因为每条x,y路径都通过T，因此T是一个点割，故
T??(G). 在[S,S]中选T条边：?v?T，若v?S，则选边xv；若v?S?{x}，
则任意选取一条边vu?[S,S]，这样选取的T条边都是不同的，因此
?'(G)?S,S?T??(G)
下面给出2-连通图的特征.
定理4(Whitney 1932)：图G(n(G)?3)是2-连通的????u,v?V(G)，在G中存
在内部不相交的(internally-disjoint)u,v-路径（即两条路径没有公共的内顶点）.
证明：“?”删除一个顶点不能使一对任意顶点不可达，故G是2-连通的. “?”对d(u,v)用数学归纳法证明.
d(u,v)?1，G?uv是连通的（因为?'(G)??(G)?2）.G?uv中的u,v-路径
与边uv构成了内部不相交的两条u,v-路径．
假设d(u,v)??-1时命题成立，下证d(u,v)??时命题也成立.
uPQRzwv 令w是某条最短u,v-路径上v的前一顶点，则d(u,v)??-1. 由归纳假设，G有内部不相交u,w路径P,Q. 若v?V(P)?V(Q)，则在圈P?Q上可以找两条内部不相交路径. 若v?V(P)?V(Q)，由于G是2-连通的，故G-w连通，所以G-w中含有一条u,v-路径R. 若R不含P或Q的内部顶点，则完成了证明. 如若不然，不妨设R与
P的内部顶点相交，设z是这些交点中在P上与v最近的一个顶点，则P上的u,z-路径
合并R上的z.v-路径就得到一条与Q?wv内部不相交路径
练习中给出2-连通图的其它特征. 定理4可以推广到一般的?-连通图.证明较繁，我们这里略去，有兴趣的读者可参见D.B. West,Introduction to Graph Theory,2nd 2001.或J.A. Bondy,U.S.R. Murty,Graph Theory with Applications,1976.
习题．
1.图G的连通度为?且
?n?G?n，则G至少有???条边.
?2???n?111 2.证明下图中?(G)?4，从而满足E(G)???
?2?111111111111111
3.设V(G)?3，则G是2-连通的? ?
111111
G是连通的且G无割点
?x,y?V(G)，存在经过x,y的环
??(G)?1且G的每一对边均位于一个公共环上