图论+第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构成了 一个圈。
作业