P u Q w P' v
u
P x P' Q w v u
P Q x w
P' v
(1)P’与P∪Q不相交，P’及P+(w,v)即为所求。 (2)P’与P∪Q相交，x是距v点最近的P’与P∪Q的交点，x在P 上。于是连接u,v有两条不相交通路，一条是P上的(u,x)一节 及P’上的(x,v)一节组成，一条是Q+(w,v)
练习
设G是一个2-连通图，又设X和Y是V(G)的不相 交子集，而且每个子集至少含有两个顶点。 证明：G含有不相交的通路P和Q使得： (1)P和Q起点均属于X； (2)P和Q的终点均属于Y； (3)P和Q的内部顶点不属于X∪Y。
证：由G加上一点x，仅和X中一切点相连，再加上一点y， 仅和Y和一切点相连，所得之图记为G*。由假设|X|≥2， |Y|≥2，故易直接验证G*仍为2-连通图。对x,y在G*中应 用定理3.5，我们得到两条起点为x、终点为y、内部不相 交的路P*、Q*。由x出发沿P*走向y的过程中，P*中最 后一个属于X的顶点记为x1，然后再由x1继续沿P*前进， 到达第一个属于Y的顶点记为y1，令P*中一段(x1, y1)-路 记为P。 类似地在Q*中可以找到一条(x2, y2)-路Q，其中x2∈X， y2∈Y。由P*、Q*的内部不相交，推知P、Q不相交。故 P、Q路即为所求。
κ(G) ≤λ(G) ≤δ(G)常严格成立，例如下图
练习
试作出一个连通图G，使之满足等式κ(G) =λ(G) =δ(G) 任何长度大于3的圈，都有κ(G) =λ(G) =δ(G)=2 完全图Kn中，有κ(G) =λ(G) =δ(G)=n-1
引理3.2 若δ(G)≥[n/2]，则G连通。 证 若G不连通，因为δ(G)≥[n/2]，所以每个 连通分支至少有[n/2]+1个顶点，即[(n+2)/2]个 顶点，但[(n+2)/2]≥(n+1)/2，于是G至少有 (n+1)个顶点，矛盾。
假设对距离小于k的任意两个顶点，定理成立，并设 d(u,v)=k≥2，考察一条长为k的(u,v)通路。设w是这条通路上v 之前的那个顶点，因为d(u,w)=k-1，由归纳假设，在G中至少 有两条内部不相交的(u,w)-通路P和Q。因为G是2-连通的， 所以G-w是连通的，因而有(u,v)-通路P’。P’与P、Q的关系不 外三种情况。
练习
2.(a)证明：若G是简单图且δ≥p-2，则κ=δ 证 当δ=p-1时，G=Kp，故κ(G)=p-1=δ 当δ=p-2时，若v1, v2∈V(G)不相邻，则对任意第三点v3∈ V(G)有v1v3, v2v3∈E(G)。这时，对任意p-3的顶点的子集 V’均有G-V’仍连通。故κ(G)≥p-2=δ，所以κ=δ (b)找出一个简单图G，使δ=p-3，且κ<δ
பைடு நூலகம்
证法二：用数学归纳法证明κ(G) ≤λ(G) 当δ(G)=0或1时，显然κ(G) =λ(G) 若对所有λ(G) =λ0≥2的图G，有κ(G) ≤λ(G) 。今设λ(H) =λ0 +1，T是H的一个割集，且|T|=λ0 +1。若边e=(u,v) ∈T，易知H-e有一个顶点割S，|S|≤λ0但此时S∪{u} 就是H的一个顶点割，即 κ(H)≤|S∪{u}|≤λ0 +1=λ(H) 由归纳法原理知，对任何λ，κ(G) ≤λ(G)
练习
对下列二图各作出两个点截集，并确定点连 通度κ(G)和边连通度λ(G) 。
定理3.1 对任何一个图G，κ(G) ≤λ(G) ≤δ(G) 证 若G不连通，则κ(G) =λ(G) =0，结论成立。下 面设G为连通图。 首先证明λ(G) ≤δ(G)。若G是平凡图，则λ(G)=0 ≤δ(G)，若G非平凡，则因每一顶点的所有关联边构 成一个边割，故λ(G) ≤δ(G)。 其次证明κ(G) ≤λ(G) 。当λ(G) =1时，G有一个割边， 显然这时κ(G) =1； 当G=Kn时，λ(G) =n-1，此时，按定义κ(G) =n-1；
练习
举例说明：若在2-连通图G中，P是一条(u,v)通路，则G不一定包含一条与P内部不相交的 (u,v)-通路Q。 u
u1 v
v1
P=uu1v1v
练习
证明：当且仅当图G的任意两个顶点由至少 两条边不重通路所连通时，G才是2-边连通的。 证 (1)若G中任意两顶点都至少由两条边不重 道路连接，显然对任意e∈E(G)，G-e是连通 的，故G为2-边连通的。 (2)反之，若G是2-边连通的，则G无割边。把 G分解成块，块与块之间以G中的割点互相连 接。设u,v是G中任意两顶点。分两种情况：
两个推论
推论3.6 若G是2-连通的，则G的任何两个顶 点都位于同一条回路上。 推论3.7 若G是p≥3的块，则G的任意两条边 都在同一条回路上。
定理3.5 可以推广到k-连通图，这样就得到一 个k-连通图的判定准则：设G是p≥k十1的一个 图，G是k-连通图当且仅当G的任意两个相异 顶点至少由k条内部不相交的通路所连通． 对于边也有类似的结果，当且仅当G的任意 两个相异顶点由至少k条边不重的通路所连通 时，G才是k-边连通的．
块
没有割点的非平凡连通图称为不可分图，一个图的 极大不可分子图称为块。显然，至少有三个顶点的 块是2-连通的。 v4
v4
v1
v1
v3 v2 v5
v3 v3
v 2 v2
v4
v6
v5
v6
相关定理
定理3.5 设G是p≥3的一个图。G是2-连通图的充要条件是： G的任意两个顶点至少由两条内部不相交的通路所连通。 证 充分性：若G的任意两个顶点至少由两条内部不相交的通 路所连通，则显然G是连通的，并且没有割点，因此，是2连通的。 必要性：设G是2-连通的，u,v是G的任意两个顶点，我们用 d(u,v)记最短(u,v)-通路中所含边数，即u,v的距离。以下对 d(u,v)用数学归纳法。 当d(u,v)=1时，由于G是2-连通的，所以e=uv不是割边，因此 G-e仍连通，于是u,v由通路P连通，而在G中u,v除此通路外， 还有一条边e所成的通路，此时结论成立。
定理3.3 若δ(G)≥[n/2]，则λ(G)=δ(G)
证明：显然G是连通的。设S是G的 割集，|S|=λ(G)。G1和G2是G-S的两 个分支，不妨设|V(G1)|=p1≤[n/2] 故G1中每个顶点至少有δ-(p1 -1)条 边伸向G2，故λ(G)≥p1(δ-(p1 -1)) 又1≤ p1≤δ,所以(p1 -1)(δ-p1)≥0变形 得 p1(δ-(p1 -1))≥δ，所以λ(G) ≥ δ(G) 由定理3.1得λ(G)=δ(G)
点连通度和边连通度
G1
G2
G3
G4
G1是树，它是最小连通图，舍弃任何一条边都使它不连 通，G2中舍弃任何一边仍然连通，但存在这样一点，舍 弃它后却会使图不连通；G3中舍弃任何一边或任何一点 都不能使它不连通，而G4是连通性最强的图。由此可见， 这四个5阶图的连通程度存在差异．现在我们定义图的 两个参数：图的(点)连通度和边连通度，用来衡量一个 图的连通程度．
点连通度的定义
G是连通图,若V(G)的子集V’使G-V’是不连通图,则V’称为 G的一个顶点割(亦称点截集),若|V’|=k，则V’称为k-顶点 割。当V’={v}时，v点称为G的割点。 当G≠Kn时，定义图G的(点)连通度κ(G)为： κ(G)=min{|V’||V’是G的顶点割}。 当G=Kn时，定义κ(G)=n-1 当G为平凡图或非连通图，定义κ(G)=0 对于非负整数k，如果κ(G) ≥k，那么把G称为k-连通图。 显然，一个k-连通图必为(k-1)-连通图，所有非平凡的连 通图都是1-连通图。
连通性
四川师范大学数学与软件科学学院
周思波
本章内容简介
图的连通性是一个图所具有的基本属性之一， 目前 已有多种函数用来度量图的连通性，诸如点连通度数 κ(G)，边连通度函数λ(G)，局部点、边连通度函数 κ(x,y)及λ(x,y)等等． 图的连通性理论的主要目的之一是研究点连通度和边 连通度的各种性质及相互联系，我们在本章的§3.l中 主要介绍这方面最基本的内容． 块是图连通性方面最基本的概念，我们在本章§3.2中 给出块的概念及其基本特征． 在§3.3中，我们介绍连通性的最基本、最重要的定 理——Menger定理，它是有关连通性问题的理论基 础． §3.4中对极小k-连通图的概念及性质给予简单介绍．
当λ(G)＞1而G非完全图时，不妨设n≥3．注意到若 E1是含λ(G)条边的割集，则G-E1必定恰有两个连通 分支．可以断言，在两个连通分支中各有一点vi ,vj， 使得边(vi ,vj)不属于E(G)(不然地话，设一个连通分 支含m个顶点，另一个含n-m个顶点，则λ(G)＝m(nm) m)，由于(m-1)(n-m-1)≥0， 即m(n-m)-m-(n-m)+1≥0， (m-1)(n-m-1)≥0 m(n-m)-m-(n-m)+1≥0 于是λ(G)≥ m+(n-m)-1＝n-1，这与G不是完全图矛 盾)． 对E1中λ(G)条边的每一条边，取一个异于vi ,vj的端点， 从而得到至多含λ(G)个点的集合V1(vi ,vj )不属于V1)， 把V1从G中舍弃也就是把E1从G中舍弃，于是G不连 通，故κ(G) ≤λ(G) 。
G
G
练习
3.若G为3-正则简单图,则κ=λ 证 (1)若κ=0，则G不连通，故λ=0，结论成立。 (2)若κ=1，则存在v∈V(G)使G-v不连通，由于dG(v)=3，从而 至少存在一个分支仅一条边与v相关联。显然这条边为G的割 边，故λ=1，结论成立。 (3)若κ=2，设v1, v2∈V(G)，G-{v1, v2}不连通，G1=G-{v1}连 通。则v2是G1的割点，且dG1(v2)≤3，类似(2)知在G1中存在一 割边e2(关联于v2)使G1-e2不连通。另一方面，由定理3.1知λ≥2， 故G-e2连通。由于G1-e2 =(G-e2)- v1 ，故v1是的割点，且dG-e2 (v1)≤3，于是由(2)知，在中存在一割边e1，即(G-e2)-e1不连通， 即G-{e1, e2}不连通，所以λ=1，结论成立。 (4)若κ=3，由定理3.1知λ=3，结论成立。综上得证。