键（bond, 割集cut set ) ? 极小非空边割。
例。e是G的割边 ? {e} 是G的键。 例。左图G中，
{uv, zv, zy, vw, yx},
uvw {zu, zv, zy, xy, xw},
{uv, zv, zy} {zu, zv, zy}
都是边割，其中后两个为键。而 E? ={zu, zv, zy, uv}不是G的边割，当然更不是G的键，虽然G- E? 变成不连
zyx通。
易见，当G连通且 S ? ? 时，
边子集B 为G的键 ? B是使G不连通的E的极小子集。
? ?(G-B)=2，且中每边的两端点分别在二分支中。 边割B = [S,S]为键 ? G[S],G[S]都连通。 （习题）
设H为G的子图，称子图 G - E(H) 为G中H的补图，记为： ?H(G) 。
特别地，当T为G的生成树时，称 ?T 为G的余树。
定理2.6 设T为连通图G的一个生成树， e为T的一条边，则
GT?T(1).余树?T 不包含G的键；
(2). ?T + e中唯一包含的G的一个键。 证明：(1).因 G - E(?T )= T 连通，则T不包含G的边割，从而也不包含G的键。 (2).注意到e为的T割边，令S与?S 分别为 T - e的二分支的顶点集。考虑 B = [S,?S]G
由于G[S] ( 包含T-e的一个分支T[S]) 与G[?S] ( 包含T-e的一个分支T[?S]) 都连通，B必是G键，包含于??T+e中。
来证B为包含在?T+e中的唯一键,只要再证对包含在?T+e中的G的任一键B?，一定有 B = B? 即可： 假设不然，由于键的极小性，B?不会包含B，从而一定存在B的一边b? B? 。于是
G - B? ? T - e +b ( 注意到 B? ? ?T+e ? G-B? ? T-e ) 但T-e+b也是G的一生成树（因其边数=? -1，且连通），从而G - B? 连通，这与B? 为G的键相矛盾。 ?
附录 设G连通，T为其任一生成树。
对每一 e ? ?T ，T+e 中有唯一圈C，因而可得 C1 ,C2 ,......,C?-?+1
共? -? + 1个 不同的圈 ，每个称为G的一个基本圈。 同样，对每一 e ? T ，?T+e中有唯一的键因而可得 B1 ,B2 ,......,B?-1
共? - 1个不同的键，每个称为的一个基本割集。
设S1 ,S2为二集合，记其对称差( 即（S1?S2）-（S1?S2） )为 S1 ? S2
称为它们的环和(ring sum)。 性质
1) 图G的每一边割是G的一些割集的边不重并。
2) 设B1 ,B2 为图的任二边割，则B1 ? B2 也是G的边割。 （对任二非空V1 ,V2 ? V， 有
11
3) 4) 5) 6) 7) 8)
习题
2.2.1 设G连通且 e ? E，证明：
(a) e在G的每棵生成树中当且仅当e是G的边割。 (b) e不在G的任一生成树中当且仅当e是G的环。
2.2.2 无环图G恰只有一棵生成树T，则G = T 。 2.2.3 设F是G的极大（maximal）林，证明： (a) 对G的每个分支H， F?H 是H的生成树； (b) ?(F) = ?(G)- ?(G)。
2.2.4 证明： 任一图G至少包含 ? - ? + ? 个不同的圈。 2.2.5 (a) 若G的每个顶点均为偶点（即，度为偶数的顶点），则G没有割边； (b) 若G是k-正则偶图且 k ? 2，则没有割边。 2.2.6 当G连通且 S ? ? 时，
边割B = [S,S]为键 ? G[S],G[S]都连通。 2.2.7 图G的每一边割是G的一些键（即，割集）的边不重并。 2.2.8 在图G中，设B1和B2为键，C1和C2为圈（看作边子集）。证明： (a) B1?B2 是G的键的边不重并集； (b) C1?C2是G的圈的边不重并集；
(c) 对G的任一边e，(B1?B2)\\{e}都包含键； (d) 对G的任一边e，(C1?C2)\\{e}都包含圈。
2.2.9 证明：若图G包含k棵边不重的生成树，则对于顶点集每一划分(V1 ,V2 ,...,Vn )，端点在这个划分的不同部分的边的数目至少为 k(n-1)。
[V1 ,V1]?[V,V] = [V2 , V2], 其中V3 =(V1 ?V2)?(?V1? ?V2 ) ）。 设边子集E?与E”分别为G中一些圈的边不重并，则E??E” 亦然。 G的每个圈可唯一地表为G的一些基本圈的环和。 G的每个边割可唯一地表为G的一些基本割集的环和。 边子集E?为G中一些边不重圈的并集
? 边子集E?与G中每个边割有偶数条公共边。 边子集B为G的一个边割
? 边子集B与G的每个圈有偶数条公共边。
G为一些圈的边不重并 ? d(v) = 偶数 ? v ? V
割点
称顶点v为G的割点(cut vertex) ? E可划分为二非空子集E1及E2，使G[E1]与G[E2]只有一公共顶点v。
显然， 当G无环时，
v为割点 ? ?(G-v) > ?(G) 。
? 存在二顶点x及y ，使G中任一(x, y)-路一定包含v。
E1E2 G
例。（边割）?v?, ?v? 为G的键 ? v不是的G的割点。
定理2.7 在树G中
12
?? v为割点 ? d(v) > 1 。
证明：(i) 若d(v) = 0，则G ? K1 ，v不是割点。
(ii) 若 d(v) = 1，则G -v 仍然是树。因此 ?(G-v)= 1 = ?(G)，从而 v不是割点。 (iii) 若 d(v) > 1，则G中存在与v相邻接的二不同顶点u, w 。由定理2.1知，uvw是G中的唯一(u, w)-路，因此G-v中不含(u, w)-路，（即G-v中u,w不连通）
? ?(G-v) > 1 ， 即v为G的割点。 ?
推论2.7 非平凡、无环、连通图中，至少有二顶点不是割点。 证明：令T为G的一生成树，由推论2.2及定理2.7知，T中至少存在二顶点 u与v不是T的割点，则它们也不是G的割点：这是因为对于u (及v)有
1 = ?(T-u) ? ?(G-u) ? 1 ， ∴ ?(G-u) = 1 =?(G) 。 ? 习题
2.3.1 设G为 ? ? 3的连通图，证明：
(a) 若G有割边，则G有顶点v使 ?(G-v) > ?(G)； （即，割边必有一端点为割点） (b) (a)的逆命题不成立。
2.3.2 证明：恰有二顶点为非割点的简单连通图必是一条路。 2.3.3 在简单连通图G中证明：
v为G的割点 ? G的任一生成树不以v为叶。
生成树的计数及Caley公式
本节只讨论无环连通图。
将图G的关联A??? 矩阵中每列的两个1元素之一改为 -1，得一新矩阵，记为Aa（它是G的一个定向图的关联矩阵）。例如：
e1v1?1?Aa?v2?0v3?0?v4??1 e21?100e301?10e4001?1e50?1? ?0???1?v1e1e2e5v2e3记A为从Aa中删去某一行所得的(? -1)?? 矩阵。 v4e4v3 引理1 设A 1 为A的任一(?-1) 阶子方阵，则
det(A1 ) = ? 1 ? A1 的列对应于G的一生成树。
证明：令划去的行对应于顶点u，记H为以全体与A1的列相对应的边构成的生成子图。由于 ?(H)= ?-1 ,因此有
H连通 ? H为G的生成树。
（1） 当H不是G的生成树时，由上述知，H不连通。令S为H中不含u的一个分支的顶点集。易见，A1中对应于S的全体行向量之和为一零向量。因此，det(A1 ) = 0。
（2）当H是G的生成树时，重排A1 的行、列如下：
取H的一个度为1的顶点u1 ，并使 u1 ? u 。记 u1 在H中的关联边为e1 ; 再取 H-u1
中的一个度为1的顶点u2 ，并使 u2 ? u ,记 u2 在H-u1 中的关联边为 e2 ;......。
按u1 ,u2 ,...及e1 ,e2 ,,,,,,,的顺序重排A1 的行、列，得矩阵A1? 。易见，A?1 为下三角型。且主对角线元素全为 ?1 ,因此 ?detA1 ? = ?detA1?? =1 。 ?
Binet-Cauchy定理 设矩阵 P=[ pij ]m?n ， Q=[ qij ]n?m ，且m ? n 则
13
det(PQ)?1?j1?...?jm?n?pij1...pmj1.........p1jmpmjmqj11qjm1.........qj1m... qjmm
...?...
T
引理2 连通图的生成树数目 = det（AA）。 证明：由Binet-Cauchy定理知，
T2
det(AA) = ∑(detA1) (对A的所有 v-1阶子方阵A1求和） 但由引理1知
?detA1? = ??10A1的列对应于G的一生成树其它
得证。 ?
无环图G的度矩阵
K = [ kij ]? ? ? ， 其中
???kij??ij?d(vi)v1?2?K???1?0???1当i?j且vi与vj间有?ij条平行边
当i?j
例如对本节开头的例子有
v1e1e2e5e4v2e3v3
定理 连通图G的生成树数目 = K的任一元素的代数余子式
T
证明：容易验证，K=AaAa 。 又，K的任一行（列）的元素的代数和 = 0，因此 K的所有代数余子式都相等。 再，设A k为从A a中去掉第k行所得的 (?-1)?? 矩阵，易见，
T
A kA k = 从K中去掉第k行第k列后所得的子方阵 故由引理2知本定理成立。 ?
例。前例的图的生成树数目 = K的(2,3)-元素的代数余子式
v4v2?13?1?1v30?12?1v4?1?v1?1?v2 ??1?v3?3?v42
=(?1)2?30?1?1?1?1?1 = 8 。 3?1
n-2
定理（Cayley） K n 中共有 n个不同的生成树。 证明：用上述定理可直接证出（习题）。 ?
习题
2.4.1 求Ｋ３，３的生成树数目。
n-3
2.4.2 若ｅ是Ｋｎ的一条边， 则 Ｋｎ－ｅ的生成树数目为 (n-2)n 。
连线问题
问题 设城市vi与vj间建立直接通信线路的费用为cij（ ? 0）。
14
建设连接 {v1,v2,......,v?}的通讯网使造价最省
? 在赋权图G中求一最小权连通生成子图； ? 在赋权图G中求一最小权生成树（最优树）。
下面的Kruskal算法是在非赋权图中求生成树的“极大无圈子图”算法的改进，它是一种贪心算法（greedy algorithm）：
Kruskal’s algorithm
(1) 选棱（link）e1 使w(e1)最小；
(2) 若已选定 e1 ,e2 ,...,ei ，则从 E\\{e1 ,e2 ,...,ei}中选取 ei+1 使 (i) G[{e1 ,e2 ,...,ei }? {ei+1 }]无圈； (ii) w(ei+1)是满足(i)之最小者。
(3) 若(2)不能再进行下去时，停止。 否则，回到 (2)。
定理2.10 Kruskal算法求出的生成树 = G[{e1 ,e2 ,...,e?-1 }] 是最优树。
*
证明：反证，假设T 不是G的最优树。取G的一最优树T。令ek为{e1 ,e2 ,...,e?-1 }中（ 按顺序）第一个不属于T的边，且令T为最优树中使k为最大者。则T+ek中唯一的圈C包含ek ，且C中
**
必含一条边e?k ? T (不然，C ? T，矛盾。）但
T? = T + ek -e?k 也是G的生成树。（因e?k不是T + ek的割边（定理2。3），从而T? 连通，且其边数=? -1。）又，由于T的子图
G[{e1 ,e2 ,...,ek-1 }? {e?k }] 也不含圈，由法算法知
w(ek )? w(e?k) ∴ w(T?) ? w(T)，
即T?也是G的最优树，且{e1 ,e2 ,...,e?-1 }中第一个不属于T?的边的下标 > k。这与k的取法相矛盾。 ?
实现 先按权的不减顺序将边集重排成 a1 ,a2 ,...,a? 。
关于算法中无圈性的判定，我们有一简单的办法： 当S={e1 ,e2 ,...,ei }已取定时，对候选边aj G[S ? {aj}] 无圈 ? aj的两端点在林G[S]（此处当作生成子图）的 不同分支中。
从而我们有求最优树的标记法：
开始：取a1为候选边； 并将vk标以k， k = 1,2,...,? 。
若S={e1 ,e2 ,...,ei }已取定，当候选边aj 的两端点有相同标号时，改取aj+1为 候选边（丢掉aj 永不再考虑）；否则选定ei+1=aj ，并将G[S]中aj两端点所在的二分支的顶点重新标号，标以两者中的最小者。
算法复杂性
边排序 O( ??log2? ) 6例 比较边两端的标号 ?
66 重新标号 O(( ? -1)? ) 323
故为好算法（ ? O( ?) ）。
72 3438
附录 1 （A） Prim’s algorithm （也是一种贪心算法） T ? ? , V? ? {u}
for all v??V? do L(v) ? w(uv) //initializing L(.); ?V?=V\\V? while ?V??V do begin
find vertex w s.t. L(w)=min{ L(v) ? v ? ?V? } and denote the associated edge from V? to w by e
15