第二章 5 生成树算法
定义2·13 （1）图G的每条边e赋与一个实数?(e)，称为e的权。图G称为加权图。 （2）设G1是G的子图，则G1的权定义为： ?(G1)???(e)
e?E(G1)定理2·10 Kruskal算法选得的边的导出子图是最小生成树。
l法所得子图T0显然是生成树，下证它的最优性。设证：Kruska算T0?G??e1,e2,?,e??1??不是最小生成树，T1是G的任给定的一个生成树，f(T)是
?e1,e2,?,e??1?中不在T1又E(T0)??e1,e2,?,e??1?，故e1,e2,?,e??1中必有不在E(T)中的
边。设f(T)?k，即e1,e2,?,ek?1在T与T0上，而ek不在T上，于是T?ek中有一个圈C，
?，使ek?在T上而不是在T0上。令T???，显然也是生成树，又（T?ek)?ekC上定存在ek?)，由算法知，ek是使G??e1,e2,?,ek??无圈的权最小的边，?(T?)??(T)??(ek)??(ek???是T之子图，也无圈，则有?(ek?)??(ek)，于是?(T?)??(T)，又G??e1,e2,?,ek-1,ek即T?也是最小生成树，但f(T?)?k?f(T)与f(T)之最大性矛盾。证毕
定理2·11 Prim算法产生的图G(T0)是最小生成树。 证明与定理2·10类似，略。
第三章
2 割边、割集、割点
定理3·4 设G是连通图，e?E(G)则e是G的割边的充要条件是e不含在圈中。 证明 必要性 设e是G的割边，若e在G的一圈C上，则G?e仍连通，这不可能。 充分性 e?xy不再G的任何圈上，若e不是割边，则G?e仍连通。G?e中x与y之间存在路径P(x,y)，于是在G中P(x,y)与e并成一个圈，与e不在圈上矛盾，故e是割边。证毕。
推论 3·4 设G连通，则G是树的充要条件是G的每条边都是G的割边。
定理3·5 设T是连通图G的一颗生成树，e?E(G)则T?e含唯一圈。
证 设e?xy?E(T)，则T中存在路径Pxy，故Pxy?e，便是含在T?e中的一个圈。由于Pxy在T中是唯一的，故这个圈也是唯一的。证毕。
设S?V,S??,S??V?S??,则用?S,S??表示一个端点在S，另一个端点在S?的全体边组合的集合，则显然?S,S??是一个边断集。
定义3·3 设G是连通，若?S,S??只把G断成两个分支，则称?S,S??为G的一个割集。 定义3·4（1）若H是G的子图，则称H?G?E(H)为H在G中的余图。 （2）若G连通，T是G的生成树，则T的余图T?G?E(T)称为余树。 定理3·6 设T是连通图G的一颗生成树，对T的每条边e有： （1）余树T不含G的割集。 （2）T?e含G的唯一割集。 证
（1）设
E??E(T)，则?(G?E?)??(G?E(T))，而
?(G?E(T))??(T)?1?G?E?连通，从而E?不是G的割集。
（2）设T是G的生成树，它的每条边都是割边，故T?e不连通，用S表T?e的一个连通片的顶点集，S?V(G)?S，则B??S,S??是G的一个割集，且B完全含在T?e中。下证割集的唯一性。否则，若T?e除含割集B外还含有另一割集B?，因T不含割集，所以B?必含e，故B??B。证毕。
定理3·7 设?是连通图G的一个顶点，则下述命题等价： （1）?是割点；
（2）存在V????的一个划分V?????U?W,U?W??，使得u?U,???W,u到?的每条路径都必经过?。
（3）存在与?不同的两顶点u,?使得u到?的每条路径都必经过?。
证 （1）?（2） 因?是割点，G??不连通，至少两个连通片，设U是一个连通片的顶点集，令W?V?(U????)，于是u,?分别属于G??的不同连通片。因此在G中u要到达?必定经过?，否则u,?在G??中会连通，与u,?分属G??的不同连通片矛盾。 （2）?（3） （3）只是（2）的特殊情况。
（3）?（1） 若u到?的每条路径都必经过?，则G??中不存在u到?的路径，G??不连通，故?是G的割点。证毕。
推论3·7·1 树T的顶点?是T的割点的充要条件是d(?)?2。
证 必要性 设?是T的割点，则必存在不同于?的两顶点u,?，使得u到?与?相邻，因T是树，u到?之间的路径唯一，即u??必经过?。由定理3·7知?是割点。证毕。
推论 3·7·2 无环的非平凡连通图至少有两个非割点。
证 设T是G的生成树，于是T至少有两个一次顶点，它们是T的非割点，因对
??V(G)。
?(G??)??(T??)
故T得两个非割点也是G的非割点，故G至少两个非割点。证毕。
4 可靠网络的设计
定理3·13 ?Harary,1962?Hm,n是m—连通图。
证 设m?2r时，需证H2r,n是m—连通图，只需证H2r,n没有比m?2r个顶点少的点断集，否则设V?是H2r,n的点断集，且V??2r，又设i,j是属于H2r,n?V?的不同连通片的顶点。令
S??i,i?1,?,j?1,j? T??j,j?1,?,i?1,i? （加法以n为模） ? V??2r，不妨设V??S?r
则显示存在S?V?的序列，从i始至j终，使得序列中连续二顶点号码之差的绝对值最大是r，但这样的序列中相邻顶点之间存在边，即此序列是一条路径P(i,j),与i,j分别属于H2r,n?V?的两个连通片矛盾。故H2r,n是2r连通的。
类似地可证明m?2r?1时，H2r?1,n是2r?1连通的。证毕。
第五章 匹配 1匹配的概念
定义 5·1 设G?(V,E)是无向图，M?E,M中任二边均不相邻，称M为G的一个匹配；M中每条边的两个端点称为配对的；若顶点?与M中某边关联，则称?为M渗透点，否则，称为M非渗透点。
定义 5·2 设M是G的匹配
（1）若M渗透了G的每个顶点，则称M为G的理想匹配；
（2）若M是G中含边数最多的匹配，则称M为G的最大匹配。 定义5·3 设M是G的一个匹配，P是G中的一条路径。
（1）若P的边在M与E?M中交替出现，则称P是一条M交错路径；
（2）若一条M交错路径得起点和终点都是M非渗透点，则称其为M可增长路径。 定理 5·1 (Berge1957)M是G的最大匹配的充要条件是G不含M可增长路径。 证 必要性 设M是G的最大匹配，但G含M可增长路径 P??0?1?2??2m?1 令M??M?E(P)，显然M?是G的一个匹配，且M??M?1，与M是最大匹配矛盾，故G中无M可增长路径。
充分性 设G不含M可增长路径，但M不是最大匹配，设M*是G的一个最大匹配，则M*?M，令H?GM?M?*?，则H的每个顶点在H中的次数只能是1或2，因为它
最多只能与M和M*中的一条边相关联。因此H的每个连通分支或是一条边在M和M*中交错的偶圈，或是一条边在M和M*中交错的路径，由于M*?M，故必定有一分支是
一条路径P，始边于终边均属于M*，即P的端点M非渗透点，从而P是M的可增长路径，与G中无M可增长路径矛盾，故M是G的最大匹配。证毕。
定义 5·4 设S?V(G),V(G)中与S的顶点相邻的所有顶点构成之集合称S的邻域，记为NG(S)。
定理 5·2 设G是二部图，其划分为(X,Y)，则G有渗透X每个顶点的（Hall,1935）匹配的充要条件是：?S?X,恒有
NG(S)?S
证 必要性 设G中含渗透X中每个顶点的匹配M。则S中各项顶点在Y中?S?X，皆有匹配点，故NG(S)?S。
充分性 若G没有渗透X的匹配，令M*为G的一个最大匹配，则M*不能渗透X，令u?X是M*非渗透点，（图（5-4）），令Z是从u出发可由M*交错路径到达的顶点集。
因M*是最大匹配，由Berge定理，u是Z中仅有的未被M*配对的顶点，取 S?Z?X, T?Z?Y 显然S??u?中的顶点在M*中与T中的顶点配对，于是： T?S?1, N(S)?T 故得
S?N(S)?1 与N(S)?S矛盾。证毕。
推论 5·2·1 若G是k?正则二部图(k?0)，则G有一个理想匹配。 证 设G的二部图划分为(X,Y),则 kX???kY ? k?0， ? X?Y
令S是X中任一非空子集，E1与E2分别表示S及N(S)中顶点相关联的边集，由
N(S)的定义，E1?E2，故
kN(S)?E2?E1?kS
于是N(S)?S，由Hall定理，G中有渗透X中所有顶点的匹配M，又因X?Y，故
M为理想匹配。证毕。
推论 5·2·2设G是划分为(X,Y)的二部图，若存在整数t?0，使X中的每个顶点
xi都有d(xi)?t;?yj?Y，都有d(xi)?t，则G中必有渗透X的匹配。
证 令S是X中任一非空子集，E1与E2分别表示S及N(S)中顶点相关联的边集，则