此时 k(G) = (G) = 1, (*) 式成立。
29
若 (G)≥2, 则必可删去某 (G)边, 使G不连通,而删 去其中(G) – 1条边, G仍然连通, 且有一条桥e = {u, v}。
对 (G) – 1条边中的每一条边都选取一个不同于u, v的顶点, 把这些 (G) – 1个顶点删去则必至少删 去 (G) – 1边。
证明 用反证法来证明。 设二顶点不连通，则它们必分属两个不同的连通
分支，而对于每个连通分支，作为G的子图只有一 个奇度数顶点，余者均为偶度数顶点，与握手定理 推论矛盾，因此，若图中只有两个奇度数顶点，则 二顶点必连通。
12
【例】 在一次国际会议中，由七人组成的小 组{a,b,c,d,e,f,g}中，a会英语、阿拉伯语； b会英语、西班牙语；c会汉语、俄语；d会 日语、西班牙语；e会德语、汉语和法语；f 会日语、俄语；g会英语、法语和德语。问： 他们中间任何二人是否均可对话（必要时可 通过别人翻译）？
(b)
(c)
1）强连通图：有向图中，任意A、B是互为可达的。如图(a)
2）单向连通图：在有向图中，任意两点A、B存在着A到B的通 路
或存在着B到A的通路。如图(b) 3）显弱然连：通在图有：向在图有中向，图如中果，有如一果条其通底过图图是中无所向有连点通的图回。路如，图(c)
则此图是强连通的。 如果有一条通过图中所有点的通路，
环是长度为1的圈, 两条平行边构成长度为2的圈. 在无向简单图中, 所有圈的长度3; 在有向简单图
中, 所有圈的长度2.
6
在两种意义下计算的圈个数 ① 定义意义下 在无向图中, 一个长度为l(l3)的圈看作2l个不同的 圈. 如v0v1v2v0 , v1v2v0v1 , v2v0v1v2看作3个不同的圈. 在有向图中, 一个长度为l(l3)的圈看作l个不同的 圈. ② 同构意义下 所有长度相同的圈都是同构的, 因而是1个圈.
28
定理 对任意的图G = (V, E),
有 k(G)≤ (G)≤ (G)
(*)
证明 若G是平凡图或非连通图,
则 k(G) = (G) = 0, 上式显然成立。
若G是连通图, 则因每一顶点的所有关联边构成一 个边割集,
所以 (G)≤(G)。
下面证明k (G)≤ (G)。
若 (G) = 1, 则G有一割边,
4、基本回路：如果回路中各个顶点都不相同。
如基本回路：v1→v6 →v3 →v2 →v1 显然，基本通路（回路）一定是简单通路（回路）。
反之不然。
4
若通路(回路)中有边重复出现, 则称为复杂通路(回路).
5
关于通路与回路的几点说明
表示方法 ① 用顶点和边的交替序列(定义), 如=v0e1v1e2…elvl ② 用边的序列, 如=e1e2…el ③ 简单图中, 用顶点的序列, 如=v0v1…vl ④ 非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v5
15
短程线与距离
u与v之间的短程线: u与v之间长度最短的通路 (u与v连通) u与v之间的距离d(u,v): u与v之间短程线的长
度 若u与v不连通, 规定d(u,v)=∞.
性质： d(u,v)0, 且d(u,v)=0 u=v d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w)
2
1、简单通路：如果通路中各边都不相同。
如简单通路：v1→v2 →v5 →v6 →v2 →v3 →v4长度为6
2、简单回路：如果回路中各边都不相同。 如简单回路：v1→v2 →v3 →v5 →v2 →v6 →v1长度为6
3
3、基本通路：如果通路中各个顶点都不相同。 如基本通路：v1→v6 →v3 →v4长度为3
7
定理 在n阶图G中，若从顶点vi到vj（vivj）存在通 路，则从vi到vj存在长度小于等于n1的通路. 推论 在n阶图G中，若从顶点vi到vj（vivj）存在通 路，则从vi到vj存在长度小于等于n1的初级通路. 定理 在一个n阶图G中，若存在vi到自身的回路， 则一定存在vi到自身长度小于等于n的回路. 推论 在一个n阶图G中，若存在vi到自身的简单 回路，则一定存在长度小于等于n的初级回路.
e6
v4 e7
e8 v6
v5 e9
例 {v2, v7}, {v3}, {v4}为点割集, {v3}, {v4}均为割点
例 在下图中的那些是割点
{v3}和{v2}都是割点, {v2, v3,v4},{v1, v2, v4,v5}都不是点割集。
22
边割集
定义 设无向图G=<V,E>, EE, 若p(GE)>p(G)且EE, p(GE)=p(G), 则称E为G的边割集. 若{e}为边割集, 则称e 为割边或桥. 在下图中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集， e8是桥，{e7,e9,e5,e6}是边割集吗？
若图G中存在割点, k(G) = 1。
图G的边连通度是为了使G成为一个非连通图, 需 要删除的边的最少数目。
若图G中存在割边, (G) = 1。
26
【例】 下图中的两个连通图都是n=8，e=16， 其中,κ（G1）=4,λ(G1）=4,κ（G2）=1，
λ（G2）=3。
G1
G2
27
假设n个顶点代表n个站，e条边表示铁路或者
定义 设有图G = (V, E), 若k(G)≥h, 则称G是h-连通 的; 若(G)≥h, 则称G是h-边连通的。
例 上图所示的图是1-连通的, 是2-边连通的。
31
简单图都是1-连通的和1-边连通的。 n阶完全图是(n–1)-连通的和(n–1)-边连通的。 对于任何n阶连通图, 当且仅当没有割点时, 它是2-连通
定义 设无向图G=<V,E>, VV, 若p(GV)>p(G)且
VV, p(GV)=p(G), 则称V为G的点割集. 若
{v}为点割集, 则称v为割点.
6}是点割集, v6是割点.
21
v1
e1 e2
v7 e4 e3
v3
v2 e5
16
图的连通性的应用 在实际问题中, 除了考察一个图是否
连通外, 往往还要研究一个图连通的 程度, 作为某些系统的可靠性度量。 图的连通性在计算机网、通信网和 电力网等方面有着重要的应用。
17
点割集
在连通图中，如果删去一些顶点或边，则 可能会影响图的连通性。所谓从图中删去 某个顶点v，就是将顶点v和与v关联的所 有的边均删去；删除边只需将该边删除
23
图中
v7
v4
e1
e4
e6
e7
v1
e3
v3
e8
v6
e2
v2 e5
v5 e9
{e1, e2}, {e1, e3, e4}, {e6}, {e7, e8}, {e2, e3, e4},
{e2, e3, e5}, {e4, e5}, {e7, e9}, {e8, e9},等都是割集, 其中{e6} 为桥。
25
下面从数量观点来描述图的连通性。 定义 设G = (V, E)是连通图,
k(G) = min{| V | | V是G的点割集}称为G的点连通
度;
(G) = min{| E | | E是G的边割集}称为G的边连
通度。
图G的点连通度是为了使G成为一个非连通图,需 要删除的点的最少数目。
的; 当且仅当没有割边时, 它是2-边连通的。 若图G是h-连通的, 则G也是h-边连通的。(k(G)≤ (G)) 由定义可知, 若h1>h2, 图G是h1-连通的, 则G也是h2-连
通的。 若h1>h2, 图G是h1-边连通的, 则G也是h2-边连通。 一个图的连通度越大, 它的连通性能就越好。
证明 假设G不连通, 则G至少有两个分图。 设其中一个分图含有q个顶点, 而其余各分图共含有 n– q个顶点。 在这两部分中各取一个顶点u和v, 则
0≤deg(u)≤q – 1,
0≤deg(v)≤n – q – 1, 因此deg(u) + deg(v)≤n – 2, 这与题设deg(u ) + deg(v)≥n – 1矛盾。
设V/R={V1,V2,…,Vk}, G[V1], G[V2], …,G[Vk]是G的 连通分支, 其个数记作p(G)=k. G是连通图 p(G)=1
10
设 A={1,2,…,8}, R={ <x,y>| x,y∈A∧x≡y(mod 3) }
即:A上模3等价关系的关系图为:
11
【例】 求证：若图中只有两个奇度数顶点，则二 顶点必连通。
18
例如”国际会议对话”任何一人请假，图G-v还 连通，小组对话仍可继续进行，但如果f、g二 人同时不在，G-{f，g}是分离图，则小组中的 对话无法再继续进行。
a
b
c
e d
f
g
19
点割集
记 Gv: 从G中删除v及关联的边 GV: 从G中删除V中所有的顶点及关联的边 Ge : 从G中删除e GE: 从G中删除E中所有边
7.2 通路、回路与图的连通性
▪ 简单通(回)路, 初级通(回)路, 复杂通(回)路 ▪ 连通图, 连通分支 ▪ 弱连通图, 单向连通图, 强连通图 ▪ 点割集与割点 ▪ 边割集与割边(桥)
1
一、通路和回路
在图中，一条通路是顶点和边的交替序列，以顶点 开始，以顶点结束。其中，第一条边的终点与第二 条边的始点重合…...。第一条边的始点称为通路的 始点，最后一条边的终点称为通路的终点。 当通路的终点和始点重合时，称为回路。 通路或回路中所含边数称为该通路或回路的长度。
8
二、图的连通性：