“充分性” 如果e不是G的割边，则Ge连通，于是在G-e中存在 一条u-v路，显然：该路并上边e得到G中一个包含边 e的圈，矛盾。 推论1e为连通图G的一条边，如果e含于G的某圈中， 则G-e连通。 证明：若不然，G-e不连通，于是e是割边。由定理1， e不在G的任意圈中，矛盾！ 例1求证：(1)若G的每个顶点的度数均为偶数，则G 没有割边；(2)若G为k正则二部图k≥2)，则G无割边。 证明：(1)若不然，设e=uv为G的割边。则G-e的含有 顶点u(或v)的那个分支中点u(或v)的度数为奇，而其余点 的度数为偶数，与握手定理推论相矛盾！
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 “充分性” 如果e不是G的割边，则G-e连通，于是在G-e中存在 一条u - v 路，显然：该路并上边e得到G中一个包含边 e的圈，矛盾。 推论1 e为连通图G的一条边，如果e含于G的某圈中， 则G-e连通。 证明：若不然，G-e不连通，于是e是割边。由定理1， e不在G的任意圈中，矛盾！ 例1 求证: (1) 若G的每个顶点的度数均为偶数，则G 没有割边; (2) 若G为k正则二部图(k≧2)，则G无割边。 证明: (1)若不然，设e=uv 为G的割边。则G-e的含有 顶点u(或v)的那个分支中点u(或v)的度数为奇，而其余点 的度数为偶数，与握手定理推论相矛盾！
(2)若不然，设e=uv为G的割边。取G-e的其中一个分 支G1,显然，G,中只有一个顶点的度数是k-1,其余点的度 数为k。并且G仍然为偶图。 假若G,的两个顶点子集包含的顶点数分别为m与n, 并且包含m个顶点的顶点子集包含度为k-1的那个点，那 么有：km-1=kn。但是因k≥2，所以等式不能成立！ 边割集简介 边割集跟回路、树等概念一样，是图论中重要概念。 在应用上，它是电路网络图论的基本概念之一。所以， 下面作简单介绍
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 (2)若不然，设e=uv 为G的割边。取G-e的其中一个分 支G1 , 显然，G1中只有一个顶点的度数是k-1,其余点的度 数为k。并且G1仍然为偶图。 假若G1的两个顶点子集包含的顶点数分别为m与n， 并且包含m个顶点的顶点子集包含度为k-1的那个点，那 么有：k m-1= k n。但是因k≧2，所以等式不能成立！ 边割集简介 边割集跟回路、树等概念一样，是图论中重要概念。 在应用上，它是电路网络图论的基本概念之一。所以， 下面作简单介绍
定义2一个具有n个顶点的连通图G,定义n-1为该连通 图的秩；具有p个分支的图的秩定义为n-p。记为R(G)。 定义3设S是连通图G的一个边子集，如果： (1)R(G-S)=n-2; (2)对S的任一真子集S1,有R(G-S)=n-1。 称S为G的一个边割集，简称G的一个边割。 例2边子集：S=(a,c,e),S2={a,b,},S3={f}是 否是下图G的边割？ 图G
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 定义2 一个具有n个顶点的连通图G,定义n-1为该连通 图的秩；具有p个分支的图的秩定义为n-p。记为R(G)。 (1) R (G-S) = n-2; 定义3 设S是连通图G的一个边子集，如果： (2) 对S的任一真子集S1 ,有R(G-S1 ) = n-1。 称S为G的一个边割集，简称G的一个边割。 例2 边子集：S1=｛a, c, e｝, S2=｛a, b, ｝,S3=｛f｝是 否是下图G的边割？ a g e d c b h f i 图G
解：S不是；S2与S3是。 定义4在G中，与顶点v关联的边的集合，称为v的关 联集，记为：S(w)。 例3关联集是割集吗？为什么？ 答：不一定！如在下图中，关联集{a,b}是割集， 但是，关联集{d,e,f)不是割集。 图G
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 解: S1不是；S2与S3是。 定义4 在G中，与顶点v关联的边的集合，称为v的关 联集，记为：S (v)。 a g e d c b h f i 图G 例3 关联集是割集吗？为什么？ 答：不一定！如在下图中，关联集｛a,b｝是割集， 但是，关联集｛d,e,f｝不是割集
定义5在G中，如果V=V1UV2,V1∩V2=Φ，E1是G中端 点分属于V与V2的G的边子集，称E是G的一个断集。 图G 在上图G中：{d,e},{f},{e,d,f}等都是G的断 集。一个图若按断集$来画，形式为：
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 定义5 在G中，如果V=V1∪V2,V1∩V2=Φ,E1是G中端 点分属于V1与V2的G的边子集，称E1是G的一个断集。 a g e d c b h f i 图G 在上图G中：｛d, e｝, ｛f｝, ｛e, d, f｝等都是G的断 集。一个图若按断集S来画，形式为： S