定义 8·6 设L?E(G),G的每一个顶点都是L中一条边的端点，则称L是G的一个边覆盖。G的最小边覆盖的边数，称为G的边覆盖数，记为??(G)。
定理8·8 （Gallar 1959）若?(G)?0,则??(G)???(G)??
证 设M是G的一个最大边独立集（即最大匹配）。U是M非渗点的集合，因??0，且M是最大匹配，一定存在边集合E?，它覆盖U的每个顶点且E??U。显然M?E??,于是M?E?是G的一个边覆盖，且
???M?E??M?E?????(??2??)????? 故 ???????
又设L是G的最小边覆盖，H?G?L?,M是H的一个最大匹配。设U是H的M非渗透点的集合，则
L?M?U?M?(??2M)???M 即 d?????,??????? 由（1）和（2）得
??????? 证毕
推论 8·8 设G是一个??0的二部图，则 ?(G)???(G) 证 由推论8·6·2和定理8·8有 ????????? 又G是二部图，由Konig定理有????，故 ?(G)???(G) 证毕。
定义8·8 （1）图G的一个k点着色是指V(G)的一个划分
(V1,V2,?,Vk),Vi中(1?i?k)的顶点i色。若每个Vi都是独立集，则称此k点着色为适当k点着色。
（2）若G有一个适当k点着色，则称G为可k点着色。
（3）若G是可k点上色，但不是可(k?1)点着色，则称k是G的点色数，记为
X(G)?k。
（4）若X(G)?k，则称G是k的色图。
（5）若G的任一真子图H，X(H)?X(G)，则称G为色临界图，X(G)?k时称为k色临界图。
定理 8·9 X(G)???1
证 任取??V(G)，着以??1种颜色之一；取无色顶点u?V(G)，着以与u相邻的顶点颜色相异的一种颜色。因为d(u)??，故u的邻顶点上的颜色最多?种，??1种色中至少有一种可以用于u的着色，故如此进行下去直到所有点都有了颜色，显然是一个??1适当上色，故
X(G)???1 证毕
定理 8·10 （Brooks,1941）设G是一个连通的简单图，它既不是奇圈也不是完备图，则
X(G)??
定义 8·9 平面图G平面嵌入后，它的k面着色是指其面集合F的一个划分
(F1,F2,?Fk),Fi中的面着以i色。如果每个Fi中的面两两不相邻（即无公共边）则称此k面
着色为适当k面着色。平面图G有k面适当着色，但不能进行k?1面适当着色，则称k是G的面色数，记为X(G)?k。
定理 8·11 设G是平面图，则X(G)?5。 定理 8·12 设G是简单图，则对G的任一边e有 ?k(G)??k(G?e)??k(G?e) 证 设e?u?，则G?e的适当k上色可分为两类 （1）u与?同色，上色方式的数目恰为?k(G?e)。
（2）u与?异色，上色方式的数目恰为?k(G)。由（1）和（2）得 ?k(G?e)??k(G?e)??k(G)
故 ?k(G)??k(G?e)??k(G?e) 证毕。
???1定理 8·13 ?k(G)是k的?次多项式，且（1）首项为k；（2）第二项为??k；
*（3）常数为零；（4）系数皆整数，且正负交错。
证 用数学归纳法证明。不妨设G为简单图，只保留重边中的一条边。G?e中有重边时，
???0时，?k(G)?k，定理成立。假设??m?1时定理已成立，考虑??m的情形，由
归纳假设
??2 ?k(G?e)?k?(??1)k???1??(?1)i?1??iiaik
??3 ?k(G?e)?k??1???k??2??(?1)i?1??i?1ibik
其中??是G?e的边数，ai,bi是非负整数，由定理8·12 ?k(G)??k(G?e)??k(G?e)
??3 =k??k???1?(???a??2)k??2???(?1)i?1??iai?(?1)??iibik
???3 =k??k???1?(???a??2)k??2??(?1)i?1??ii(ai?bi)k 证毕。
定理 8·14 设u和?是GX(G)?min?X(G?u?),X(G?u?)?
的两个不相邻的顶点，则
证 首先证X(G)?min?X(G?u?),X(G?u?)? 设X(G)?k，可用k种色给G适当上色，对u和?来说，有下列两种情形
（1）u和?同色，G?u?是可k上色，则 X(G?u?)?k
（2）u和?异色，则G?u?可k着色，故 X(G?u?)?k
综上 min?X(G?u?),X(G?u?)??k?X(G)
其次证明X(G)?min?X(G?u?),X(G?u?)?
显然 X(G)?X(G?u?)，设X(G?u?)?k，则G是可k着色，因此
X(G)?k?X(G?u?)，故
X(G)?min?X(G?u?),X(G?u?)? 证毕。
i?1定义 8·10 图G的一个k顶点着色(V1,V2,?Vk)，若Vi是G??Vj的极大独立集，
j?1i?1,2,?,k,V0??，则称这一k顶点着色是规范k顶点着色。
定理 8·15 若G是可k适当着色，则G存在k顶点规范着色。
证 设(V1,V2,?Vk)是G的一个适当k点着色，若V1是G的极大独立集，则把V1各顶点着1色；不然，V1是独立集，可使V1扩张成极大独立集V1G?V1（1）（1）；V2（1）?V2?V1(1),若V2（1）是
的极大独立集，则把V2（1）的顶点着以2色，不然将V2(1)(2)（1）扩张成G?V1(k)（1）的极大独立
集V2（2），如此继续，最后可得G的规范k点着色(V1,V2,?Vk)。证毕。
定理 8·15 设点集族F??V1,V2,?Vn?是圈G的全体极大独立集，则G的色数 ?r? X(G)?min?r?Vik?V,Vik?F?
?k?1??r?证 设min?r?Vik?V,Vik?F??m，则F中存在m个点集，不妨设是V1,V2,?Vm，使
?k?1?m得
?Vi?1i?V。令V1?V1,V2?V2-V1?，Vi?Vi??Vj,(i?1,2,?,m)。容易验证
j?1???i?1???(V1,V2,?Vm)是G的一个适当m上色，故：
X(G)?m
????反之，设X(G)?l，则G存在一个适当的l上色(V1,V2,?Vl)，由于每个Vi是独立集，?必定含在一个G的极大独立集Vi中，如此
????? (V1,V2,?Vl)且有Vi?V，因Vi?Vi
k而
综上X(G)?m，证毕。
第九章 网络流问题
定义 9·1 D?(V,E)是一有向图，D中给定两点，一个点称为源或发点记为s，另
一个点称为汇或收点，记为t。边e上的权c(e)?，称为边e的容量，并称这有向加权图为容量网络，可记为D?(V,E,c(e))。
定义 9·2 容量网络上的流：定义在E上的非负函数f(e)，称f(e)为e上的流函数。 定义9·3 设f是容量网络D上的一个流函数，若满足：
(c1) ?e?E,0?f(e)?c(e)
(c2) ???V??s,t?
?f(e)??f(e)?0
e??(?)e??(?)其中?(?)表示以?为起点的边集。则称f是D上的一个可行流。 记 ?(f)??e??(t)f(e)??e??(t)f(e)
称?(f)为f的流量。条件(c1)称为容量约束条件；(c2)称为守恒条件。
定义9·4 设D是一个容量网络，S?V(D),s?S,t?V(D)?S?S,?S,S?表示D的全体起点在S，终点在S的弧集，则称?S,S?为网络的截集，称
c(S)?为截量。
引理 9·1 对网络D的任一截集?S,S?恒有： ?(f)?证：根据流的条件，有 ?(f)?e??S,S?c(e)
??f(e)??f(e)
e?(S,S)e?(S,S)??f(?,t)??f(t,?)
?此外对任一顶点u?S(u?t)均有：
??f(?,u)??f(u,?)?0
?根据上面两个方程，对S中的所有顶点（包括t）的流求和，得到 ?(f)?因为
?(?u?Sf(?,u)??f(u,?))
????u?Sf(?,u)??u?Sf(?,u)??u?Sf(?,u)
???S??S