此外,N(S)彐T(因T中顶点通过S中顶点与a连M交错路),且N(S)∈T(对N(S) 中每个顶点t,设它是S中顶点s的邻点,从到s的M交错路必可延伸为u到t的M交错 路)。故 N(S)=7(2) 由(1)、(2)知:|N(S)=7上=S-1<S,这与定理条件矛盾。证毕。 推论33.1设G=(X,H)是二部图,若X中每个顶点至少关联k条边(k≥1)而y中每个顶 点至多关联k条边,则G中存在饱和X的匹配 证明:由条件知,对ScX,S至少关联k|S|条边。这kS|条边至少关联Y中S|个顶点。 即|N(S)2S,由h定理,G有饱和X的匹配。证毕。 推论332 (Frobenius,1917)具有二划分(X,Y)的二部图G有完美匹配的充分必要条件是 x=且对vS≤X(或Y),均有N(S)S 证明:显然 推论333Knig,1916)设G是k正则二部图(k>0),则G有k个边不重的完美匹配 证明:(1)先证G有完美匹配 证法1:设G=(X,Y)是k正则二部图,则kx=|E(G=ky1,因k>0,故X=,任 取SX,令E1=G中与S关联的边},E2=G中与NS关联的边}。则E1E2。因而 4N(S)=|E2|2|E=kS,即N(S)≥|S。由推论332,G有完美匹配 证法2:由推论33.1,G中有饱和X的匹配。因X=(如前所证),故这个匹配就是完美 (2)再证G中有k个边不重的完美匹配(用归纳法) 当k=1时,显然 设对所有k正则二部图,结论成立。下证对(k+1)正则二部图G,结论也成立。 设M是G的一个完美匹配。令G′=G\M。则G′是k正则二部图。由归纳假设,G′中 有k个边不重的完美匹配。故G中有k+1个边不重的完美匹配。证毕。 下一推论是显然的。 推论334完全二部图Kk中存在k个边不重的完美匹配。 推论335设G=(XY)是二部图,且x1==n。若6(G)≥万,则G有完美匹配 证明(用反证法):若G没有完美匹配,则由推论3.3.2,存在SgX,S≠φ,使|N(S)kS|。 因G是二部图且δ(G)≥1,故|SN(S)δ(G)≥",且Y\N(S)≠p(因
6 此外，N(S) ⊇ T（因T 中顶点通过 S 中顶点与u 连 * M 交错路），且 N(S) ⊆ T（对 N(S) 中每个顶点t ,设它是 S 中顶点 s 的邻点,从u 到 s 的 * M 交错路必可延伸为u 到 t 的 * M 交错 路）。故 N(S) = T (2) 由(1)、(2)知： NS T S S () | | 1 = = −< ，这与定理条件矛盾。证毕。 推论 3.3.1 设G = (X,Y) 是二部图，若 X 中每个顶点至少关联 k 条边（ k ≥ 1) 而Y 中每个顶 点至多关联 k 条边，则G 中存在饱和 X 的匹配。 证明：由条件知，对∀S ⊆ X ，S 至少关联k | S |条边。这k | S |条边至少关联Y 中| S |个顶点。 即 N(S) ≥ S ，由 Hall 定理，G 有饱和 X 的匹配。证毕。 推论 3.3.2.(Frobenius,1917) 具有二划分 (X ,Y) 的二部图 G 有完美匹配的充分必要条件是 X = Y 且对∀S ⊆ X （或Y ），均有| N(S) |≥| S |。 证明：显然。 推论 3.3.3 (König,1916) 设G 是 k 正则二部图(k > 0) ，则G 有k 个边不重的完美匹配。 证明：（1）先证G 有完美匹配。 证法１：设G = (X ,Y) 是 k 正则二部图，则 k X = E(G) = k Y ，因 k > 0 ，故 X = Y ，任 取 S ⊆ X ，令 E1 = {G 中与 S 关联的边}， E2 = {G 中与 N(S)关联的边}。则 E1 ⊆ E2。因而 k N S = E ≥ E = k S 2 1 ( ) ，即 N(S) ≥ S 。由推论 3.3.2,G 有完美匹配。 证法２: 由推论 3.3.1，G 中有饱和 X 的匹配。因 X = Y （如前所证），故这个匹配就是完美 匹配。 （2）再证G 中有 k 个边不重的完美匹配（用归纳法）。 当 k = 1时，显然。 设对所有 k 正则二部图，结论成立。下证对(k +1) 正则二部图G ，结论也成立。 设 M 是G 的一个完美匹配。令G′ = G \ M 。则G′ 是 k 正则二部图。由归纳假设，G′ 中 有 k 个边不重的完美匹配。故G 中有 k +1个边不重的完美匹配。证毕。 下一推论是显然的。 推论 3.3.4 完全二部图 Kk ,k 中存在 k 个边不重的完美匹配。 推论 3.3.5 设G = (X.Y)是二部图，且 X = Y = n 。若 2 ( ) n δ G ≥ ，则 G 有完美匹配。 证明(用反证法)：若 G 没有完美匹配，则由推论 3.3.2，存在 S ⊆ X , S ≠ φ ，使| N(S) |<| S |。 因 G 是二部图且 2 ( ) n δ G ≥ ， 故 2 | | | ( ) | ( ) n S > N S ≥ δ G ≥ ， 且 Y \ N(S) ≠ φ （ 因
N(S)kS|SXHY|)。令∈Y\N(S),则N()X\S,因此, δ(G)≤da(u)=N(u)图x|-|Skn n 这与条件矛盾。故G有完美匹配。证毕。 例33.1下图所示的是14个大小相同的正方形组成的图形。试证明:不论如何用剪刀沿着图形 中所画的直线对它进行裁剪,总剪不出7个由相邻的两个小正方形组成的矩形来 证明:将图形中方格从1到14编号。以方格为顶点集作简单图G=(V,E,边∈E(G)当且 仅当i、j所在的方格在图形中相邻(有公共边) 注意G中每条边对应于原图形中由相邻两个小正方形组成的矩形,故剪出7个矩形相当于 在G中求由7条边组成的匹配。由于有14个顶点,故所求的是完美匹配。但这样的匹配是不 存在的。事实上,G是一个二部图,其二划分为 X={1,34.6,9,1112,14},Y={2,5,7,8,10,13}。 X=8>6=Y|。由推论332,不存在完美匹配。 注:G的k正则生成子图称为G的k因子。若G存在无公共边的k因子H1, 使得G=H1∪H2U…∪Hn,则称G是可k-因子分解的 推论323证明了完全图K是可1一因子分解的;推论334证明了完全二部图Kn,是可 1一因子分解的;推论3.33证明了每个k正则二部图是可1一因子分解的 若图G有1因子,则它显然应是偶数阶图。因此奇数阶完全图K2mn1不可能有1因子 因子分解是图论研究的一个重要选题,进一步的了解可参看 [1]G Chartrand, and O.R. Ollermann, Applied and Algorithmic Graph Theory, MCGraw-Hill, New York, 1993 [2J. Akiyama, M. Kano, Factors and factorizations of graphs -a survey, J Graph Theory, 9(1985) 3]W D. Wallis, One-factorizations, Kluwer Academic Publishers, Dordrecht, Boston, 1997 [4]Guizhen Liu, and Binhai Zhu, Some problems on factorizations with constraints in bipartite graphs, 128(2003),421-434
7 | N(S) |<| S | ≤| X |=|Y |）。令u ∈Y \ N(S) ，则 N(u) ⊆ X \ S ，因此， 2 2 ( ) ( ) | ( ) | | | | | n n δ G ≤ dG u = N u ≤ X − S < n − = 。 这与条件矛盾。故 G 有完美匹配。证毕。 例 3.3.1 下图所示的是 14 个大小相同的正方形组成的图形。试证明：不论如何用剪刀沿着图形 中所画的直线对它进行裁剪，总剪不出 7 个由相邻的两个小正方形组成的矩形来。 证明：将图形中方格从 1 到 14 编号。以方格为顶点集作简单图 G = (V, E)，边ij ∈ E(G) 当且 仅当 i、j 所在的方格在图形中相邻（有公共边）。 注意 G 中每条边对应于原图形中由相邻两个小正方形组成的矩形，故剪出 7 个矩形相当于 在 G 中求由 7 条边组成的匹配。由于有 14 个顶点，故所求的是完美匹配。但这样的匹配是不 存在的。事实上，G 是一个二部图，其二划分为 X={1,3,4,6,9,11,12,14}，Y={2,5,7,8,10,13}。 |X| = 8 > 6 = |Y|。由推论 3.3.2，不存在完美匹配。 注：G 的 k 正则生成子图称为 G 的 k 因子。若 G 存在无公共边的 k 因子 H H Hn , , , 1 2 " ， 使得G = H1 ∪ H2 ∪"∪ Hn ，则称 G 是可 k－因子分解的。 推论 3.2.3 证明了完全图 K2n 是可 1－因子分解的；推论 3.3.4 证明了完全二部图 Kn,n 是可 1－因子分解的；推论 3.3.3 证明了每个 k 正则二部图是可 1－因子分解的。 若图 G 有 1 因子，则它显然应是偶数阶图。因此奇数阶完全图 K2n+1 不可能有 1 因子。 因子分解是图论研究的一个重要选题，进一步的了解可参看 [1] G. Chartrand, and O.R. Ollermann, Applied and Algorithmic Graph Theory, MCGraw-Hill, New York, 1993. [2] J. Akiyama, M. Kano, Factors and factorizations of graphs — a survey, J. Graph Theory, 9(1985), 1-42. [3] W.D. Wallis, One-factorizations, Kluwer Academic Publishers, Dordrecht, Boston, 1997. [4] Guizhen Liu, and Binhai Zhu, Some problems on factorizations with constraints in bipartite graphs, 128(2003), 421-434. 4 5 6 7 1 2 3 8 9 10 11 12 13 14 4 1 6 7 8 5 2 3 9 10 11 12 13 14