图论+第3章+图的连通性
直观上看,右边的比左边的图连通“程度”
要好。
(点)连通度
图的(点)连通度我们常常省略“点”字称连
通度。 树是具有最小连通度的图。 若κ (G ) ≥ k ,则称G是k-连通的。 若G是平凡图或非连通图,则κ (G ) = 0 。 所有非平凡连通图都是1连通的。
边连通度
边连通度λ (G )=min{ S | S是G的边割集} 完全图的边连通度定义为 λ ( K v ) = v − 1。 空图的边连通度定义为0。 边连通度λ (G ) 有时又记作 κ ′(G ) 。
2-连通图的性质
定理 3.2.4:若G是 p ≥ 3的2-连通图,则G的
任意两条边都在同一个圈上。
证明:(板书)
2-连通图的性质
对于一个无环且无孤立点的图G,下面的条
件是等价的:
(1)图是不可分的; (2)图是2-连通的; (3)过任意两个顶点总有一个圈; (4)过任意两条边总有一个圈。
不可分图
没有割点的非平凡的连通图称为不可分图 (non separable graph)。
定理3.1.5 不可分图的任一边至少在一个圈中。 证明:设e是不可分图G的任意边,e=(x,y),x和y都 不是割点,所以图G-e是连通的,故G-e必有一条(x,y) 道路P。于是P+e就是构成G中的一个圈。
e相连接。于是u和v在G-e中成为连通的。故矛盾。
(2)假设e=(x,y)不是割边,那么G-e和G的分支数
相同。由于G中存在一条(x,y)道路,所以x和y均 在G的同一分支。于是x和y在G-e的同一分支中, 故在G-e中存在一条(x,y)道路P,这样边e就在G的 圈P+e中。
割点定理(1)
定理3.1.2 当且仅当在G中存在与顶点v 不同
块
含4个块的图
2-连通图
设P和Q是图G的两条(u,v)道路。如果除了端
点u,v外,P和Q没有其他公共顶点,则称P 和Q是内部不相交的。
2-连通图
定理3.2.2: 设G是p>3的图,G是2-连通的充
要条件是G的任意两个顶点至少由两条内部 不相交的道路所连通。
证明:“⇐”(充分性)
对∀w ∈ V (G ) ,任取 u, v ∈ V (G − w) 。由条件,u,v至 少由两条内部不相交的道路所连通。所以u,v在 一个圈C中。 1)w不在圈C中,则在G-v中u,v仍在圈中,连通 2)w在圈C中,则在G-v中u,v在路C-w中,连通 综上,u,v在G-w中有路相连。由u,v的任意性, G-w是连通图。故w不是G的割点,由w的任意性 知, G无割点,即G是2-连通图。
割点
w(G − v) > w(G ), 则 定义:设 v ∈ V (G ) ,如果
称 v为 G 的一个割点(cut-vertex) 。
即去掉一个顶点(及其相关联边)后,分支数增加
v1,v2是割点
w(G ) 表示图G的分支个数
割边定理
定理3.1.1 边 e是 G 的割边当且仅当 e 不在G 的
G的顶点的最小度。 证明:先证 κ (G ) ≤ λ (G ) 若G不连通,则 κ (G ) = λ (G ) = 0 若G是完全图,则 κ (G ) = λ (G ) = v − 1
设G连通但不是完全图,则G有边割集含有λ 条边, 其中 1 ≤ λ < v − 1 。设这个边割集为 E,对 ′ E ′中 每条边,选取一个端点,去掉这些端点(至多 λ 个)后,G便成为不连通图,故这些端点构成一个 点割集V ′ ,则| V ′ |≤ λ ,因此
割点定理(3)
定理3.1.4 树G中所有度大于1的顶点都是割
点。
d (v) = 0,v显然不是割点; (2)若 d (v ) = 1,则G-v的边数比顶点数少1,且无
证明:(1)若
圈,所以G-v仍是一棵树,因而G-v是连通的,故 v不是割点; (3)若 d (v ) > 1,则存在与v邻接的不同顶点u和w。 道路uvw是G唯一一条(u,w)道路,于是去掉v后, G-v没有(u,w)道路,因为G-v是分离图,故v是割 点。
第三章:图的连通性
割边和割点 点割集和边割集 边连通和点连通 连通度
点割集
定义:对于图G,若V (G ) 的子集V ′ 使得
w(G − V ′) > w(G ),则称 V ′ 为图G的顶点割集。
含有k个顶点的点割集称为k-点割集 割点是1-点割集。 完全图没有点割集。
κ (G ) ≤| V ′ |≤ λ (G )
连通度定理
λ (G ) ≤ δ (G ) 设d (v) = δ ,删去与v关联的 δ 条边后,G变成不连 通图,故这δ 条边构成G的一个边割集,因此 λ (G ) ≤ δ (G )
证明(续):再证
证毕。
块的概念
图中一个最大不可分子图称为一个块(block)。 即指是无割点的连通图。
的两个顶点 u 和 w ,使所有的(u, w)道路都通 v 才是割点。 过v 时,
即顶点 v 是连通图G的割点当且仅当 G − v不连通 证明:(1) 设v是G的割点,则G-v是至少有两个分
支的分离图。令U表示其中一个分支的顶点构成 的集合,W表示其余顶点构成的集合,从而(U,W) 构成V(G)-{v}的一个划分。则存在两个顶点u ∈ U 和w ∈ W各在G-v的不同分支中。因此G中每条道 路(u,w)都含有v。
割点定理(1)
证明(续):(2)若v在G的每条联结u和w的道路上,
则在G-v中不能有一条联结u和w的道路,从而G-v 是不连通的,即v是G的割点。
割点定理(2)
定理3.1.3 一个连通图G至少有两个顶点不
是割点。
证明:令u和v是在G中两个最大距离的顶点。又
假设v是割点,则有一个顶点w,它与u在G-v的 不同分支中。从而v在每一条联结u和w的道路上, 所以 d (u , w) ≥ d (u , v 。这与 u和v是最大距离的顶 ) 点相矛盾,故顶点v不是割点。同理,顶点u也 不是割点。
任何圈中
证明:(1)设e是G的一条割边。则存在顶点u和v,
它们在G中连通,但是在G-e中不连通,因此, 在G中存在某条(u,v)道路P,且P通过边e。设 e=(x,y),且P上从x到y。在G-e中,P有一节使得u 与x相连,有一节使得y与v相连。
割边定理
证明(续): 若e在某圈C中,则G-e中x,y将由道路C-
第三章:图的连通性
杨帆 江苏科技大学数理学院
第三章:图的连通性
割边和割点 边连通和点连通 连通度
割边
定义:设e ∈ E (G ),如果 w(G − e) > w(G ) ,则
称 e 为 G的一条割边(cut-edge) 。
即去掉一边后,分支数增加
e1, e2是割边
w(G ) 表示图G的分支个数
边连通度
若G是平凡图或非连通图,则 λ (G ) = 0 。 若G是含有割边的连通图,则 λ (G ) = 1 。 若λ (G ) ≥ k ,则称G是k-边连通的。 所有非平凡连通图都是1-边连通的。
连通度定理
定理3.2.1 κ (G ) ≤ λ (G ) ≤ δ (G ),其中δ (G )是图
图的块
至少有三个顶有反例,例如K2是个块,
但不是2-连通的。
2-连通图的性质
定理3.2.3:若图G是2-连通的,则G的任意
两个顶点都位于同一个圈上。
证明:由定理3.2.2知,若G是2-连通的,那么G
中任意两个顶点至少有两条内部不相交的道路。 由当且仅当两个顶点由两条内部不相交的道路 连通的,这两个顶点才在同一个圈上,于是若G 是2-连通的,则G的任意两个顶点都在同一个圈 上。
边割集
定义:对于图G,若E (G )的子集E ′使得
w(G − E ′) > w(G ),则称E ′为图G的边割集。
含有k条边的边割集称为k-边割集 一条割边构成一个1-边割集 对于非平凡图G,若 E ′是一个边割集,则 ′ G \ E不 连通。
(点)连通度
连通度κ (G )=min{ V ′ | V ′ 是G的顶点割集} 完全图的连通度定义为κ ( K v ) = v − 1 。 空图的连通度定义为0。
2-连通图
⇒ 证续:“ ”因为G是2-连通图,所以G不含割点。
对 ∀u, v ∈V (G ),欲证明u,v在同一圈上。对 d (u, v) 作归纳法。 d (u, v) = 1,因为λ ≥ κ ≥ 2,故边uv不是割边,G-uv 连通。因此G-uv中存在一条 (u , v)路P,这表明u, v在圈P+uv上。 假定d (u, v) < k 时,结论成立。下证对于d (u , v) = k 时结论也成立。 设P0 = u wv是长为k的一条 (u, v) 路,则d (u, w) = k − 1 。由归纳法,u,w在一个圈上, 故 u,w间有两条内部不交的路P,Q。因G是2-连 通图,G-w连通,在G-w中存在一条(u, v) 路P’。 令x是P’上最后一个与 P Q 相交的公共点。不防 设x ∈ P ,则P上 (u, x) 段+P’上( x, v) 段与Q+wv构成了 一个圈。
作业