设u∈X未被M匹配，T称为G的M交替树，若① u∈T ②?v∈T,有唯一的u到v的交替道路，u称为根；M增长道路：交替树T终点也未被M匹配，则称T为M增长道路。
定理2-9：(Hall，1935) V(G)=X∪Y 是二分图，则G中存在完备匹配（把X中顶皆许配的匹配）的充分必要条件是?s ? X ， | N(s)|≥|s|( N(s)为s的邻顶集)。
?v∈V(G)， d(v)=k 则称G为k次正则图。
推论：G是k次正则二分图，则G有完备匹配。 求完备匹配的匈牙利算法（Edmonds，1965） 设G=(X，Y，E)为二分集，X，Y为其二个顶点集） （1）
从G中的任一匹配M开始；
（2） 若M与X所有顶点匹配，则终止。
否则，?u∈X，未匹配，记S={u}?X，T= ??Y ；
（3） 若N(S)=T， 由定理2-9， 由于|N(S)|=|T|=|S|－１<|S|，故G无完备匹配，算法终止。否则，取y∈N(S)－T?Y；
（4）若y为被M许配的，设yz∈M， 则S∪{z}→S， T∪{y}→T 转3）；否则即得u到y的一条增长道路 E(P)； （5）令M1=M?E(p)代替M，转2）。
例2-15．求图2-40的最大匹配
首先取初始匹配 M={x2y2， x3y3， x5y5}， （1） x1未被匹配 S={x1} N(S)={y2， y3}, T=?， y2∈N(S)－T 被匹配 S→{x1， x2} ，N(S)={y2， y3， y4， y5}， T={y2}, y4∈N(S)－T， 则E(p)=x1y2x2y4为增长道路。 （2）M1=M?E(p)={x1y2， x2y4， x3y3， x5y5} （3） S={x4}未匹配， N(S)={y2， y3} ,T=?， y2∈N(S)－T, S→{x4， x1}, T={y2} N(s)={y2， y3} ; y3∈N(s)－T , x3y3∈M1， S→{x1， x3， x4} (*) ,N(S)={y2， y3} T={y2， y3} , N(S)－T=? , 无完备匹配。
讨论：若G增加x1y1，则于（*） N(S)={y1， y2， y3} , T={y2， y3} , y1∈N(S)－T 未匹配, 所以
E(p)=x4y2x1y1为M增长道路，M1?E(p)={x4y2， x2y4， x1y1， x3y3， x5y5}为完备匹配。
9．平面图
1）Euler公式与正多面体
９３
图2-40
Euler公式：G是连通平面图 则v－e+f=2 ， 其中v 顶点数， e 边数，f面数（这里一个多边形或图的外面均称为一个面）。
证明：对f用归纳法
f=1，G无圈， 又G为连通图，故G是树，于是 v=e+1=> v-e+f=v-e+1=2 成立。 设f=k时，v－e+f=2成立。
现证f=k+1成立。 由于f=k+1≥2知G有圈， 设e0为G的某个圈的边，则G－e0
仍连通。G中被e0分割的二个面在G－e0中变成了一个面。于是，G－e0有k个面，故由归纳假设 V(G－e0)－e(G－e0)+k=2 但V(G－e0)=V(G)， e(G－e0)=e(G)－1 所以上式变为 V(G)－(e(G)－1)+k=2 ，即V(G)－e(G)+k+1=2，亦即V(G)－e(G)+f(G)=2。▌
注：（1） Euler公式对凸多面体亦适用（为平面图）如：正六面体 v=8，e=12，f=6 v-e+f=2
（2） 当G非连通且连通分支为ω时有v-e+f=ω+1
正多面体，一个正多面体各面的边数相同 n， 各顶点的棱数相同 m， 显然n，m≥3， 2E=mv=nf(=棱的二倍，正多面体的面为n边形)， 又v-e +f=2
N M V E 可解得：
3 3 4 6 4nv=， 3 4 6 12 2n?mn?2m3 5 12 30 2mn4 3 8 12 e= ，
5 3 20 30 2n?mn?2mf=
4m2n?mn?2nF(f面体) 4 8 20 6 12
讨论：m=3 ，分母为 6-n，分子为正，可知3≤n≤5 ；
n=3 分母为6-m，分子为正，可知3
≤m≤5。
故可讨论m=3，n=3，4，5； n=3，m=3，4，5
又m=4时n=3；m=5时 n=3；m=6时 n取任何≥3的自然数均无意义。
同理，n=4，m=3；n=5，m=3；n=6时，m取任何≥3均无意义， 故得上表。
由此知,正多面体只有五种:正四面体、正六面体、正八面体、正十二面体、正二十面体。
2．平面图
二个例子： 1）古代独裁者
９４
(a)(b)图2-41
相传古代有一位独裁者，临死时留下遗嘱，把土地分给他的五个儿子，这五个儿子在自己的领地上各修建了一座宫殿，他们还企图修一些道路，使得每二座宫殿之间有一条道路直接相通，又要求道路不能相互交叉。结果这五个愚蠢的王子煞费苦心，终告失败（图2-41（a））。
2） 房屋和井
有3户人家，旁边有三口井。欲修从每一房屋到每一井的路线，使它们互不相交（图2-41（b））。
这二个例子具有代表性，我们将用Euler公式证明其非平面图。
定义2-7：一个图称为可嵌入曲面S， 如果把它的图示画在S上，可以使任二条边不相交。可嵌入平面的图称为平面图，否则称为非平面图。
例2-16：任意树为平面图； K5(每顶点4度，5个顶点，10条边)可以嵌入环面(图2-30，31)；
K33（二分图，每顶点3度，6顶点，9条边）可嵌入Mobius带(图2-42，43)。
定理2-10. G是平面图的充分必要条件是 G可嵌入球面。
定理2-11. K5，K33不是平面图。
证明：对K5， V(K5)=5， E(K5)=10 由于K5为连通图且为简单图，故每个面至少有三条边，所以3f≤2×10(每二个相邻面公用一条边), 另一方面，由Euler公式 f=2
－v+E=2－5+10=7，所以3f=3×7>20 ， 矛盾说明K5非平面图；对K33， V(K33)=6，E(K33)=9，f=2－v+E=5， 由于K33为二分图，故每个面至少4条边从而4f≤18 但4×5≥2×9 矛盾。
为说明一般图是否为平面图，
图2-43
先引入： 图2-42
９５
初等收缩（Kuratowsky，1930）：图G上的相邻二点，u，v用新点ω代替得到的新图。（此时ω与原来和u，v相邻的点相邻）称为图G的初等收缩。
同胚：二个图称为同胚，若一个图可以从另一个图的边上“加上”一些新点得到；规定图自己和自己同胚。
图2-44（a）与K5同胚，图2-44(b)（又称
显然，收缩与同胚互逆。 定理2-11（Kuratowsky，1930）G是平面图的充分必要条件是G中无子图与K5或K33同胚（或可收缩到K5或K33上）。
如：最小的妖怪（Petersen 图）不是平面图（有与K33同胚的子图）， “最小的妖怪”是“妖怪”（Snark graph，图2-45）的子图，特点：V=10，每顶有三条边，无桥， 任意删除三条边不会使之变为二个有边图。
d图2-44
Petersen图，也称最小的妖怪）有与图2-44 (c)(K33)同胚的子图。
图的厚度：若图G=
?Gi?1i
图2-45
E(Gi)∩E(Gj)=? ，Gi （为平面
图），则称G1?Gd为图G的平面分解。?(G)=min{d|(G1?Gd)是G的平面分解}称为图的厚度或层次。
定理2-12. θ(G)≥[
E3V?6 ] （V>2）。
此结论可应用于：设计电路板，需要电路在平面上实现，制成印刷电路，问一个电
９６
路至少在几块电路板上实现？
目前，还无确定图的厚度的公式，也无有效算法。
平面图在工程技术上有广泛应用，因此，它和Harmilton图问题一道形成了图论的十分活跃的课题。 从历史上看，Kuratowsky定理的提出（1930）打破了图论研究的沉闷局面，成了图论振兴的转折点。
10．着色与四色问题
定义2-8：图G的一个k顶着色是指把V(G)分成k部分{V1，?，Vk}，Vi中的顶着以 i色，若每个Vi中无相邻顶，则称此k顶着色为正常k顶着色。
若G可以k顶着色，但不能k－1着色，则记k=X(G)称为G的顶色数。 显然，任一图可以V正常着色 结论：X(G)≤Δ+1 (Δ=max{d(v)}) 应用1. 考试安排问题：
某校共有n门课需要进行考试，每个学生不止选修一门课，为使每个学生都能参加自己所选课程的考试，问至少需几天才能安排完？ 记每一门课为一个顶，当且仅当二门课被同一学生选修时连一条边，得到一个图G(如图2-46)。
G正常着色对应于：同一学生不会在同一时间参加他选的二门课的考试。因此，X(G)即为安排完考试所需的最少天数。
应用2．存储问题：有的货物放在一起不安全（如羊和白菜，狼和羊等），问至少几个库房存放才是安全的？将货物看作顶点，不能放在同一库房的货物之间联一条边，得到一个图，问题转化为k顶着色问题。
定义2-9：平面图G嵌入平面后，它的k面着色，是指将面集合分成k部分{F1，F2，┅Fk} ，Fi均涂以i颜色；若每个Fi中的面二二无公共边，则称此着色为k面正常着色。
若G能k面正常着色，不能k－1面着色，则称k=X*(G)为G的面色数。 图的对偶：若将图G的面对应顶，面相邻则在二对应点间联一边，得到的图称为图G的对偶，记为G*。
显然， X(G*)=X*(G) (∵f(G)=V(G*))
四色定理：（1852 伦敦大学学生 Guthrie）1. 对任何平面图G， X*(G)≤4 ; 2. 对任何平面图G， X(G*)≤4。
这个问题，困扰了数学家们100年，1878年由格思里（Francis Guthrie）首先提出。直到1976年，伊利诺大学 Appel和Haken在Koch的协作下，用计算机证明了四色猜想（用了1亿个逻辑判断，花了1200个机时。说明其证明之艰难）。
９７
图2-46