图论+第3章+图的连通性

《图论+第3章+图的连通性》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章：图的连通性杨帆江苏科技大学数理学院第三章：图的连通性割边和割点边连通和点连通连通度割边定义：设e∈E(G)，如果w(G−e)>w(G)，则称e为G的一条割边(cut-edge)。即去掉一边后，分支数增加e1,e2是割边w(G)表示图G的分支个数割点定义：设v∈V(G)，如果w(G−v)>w(G)，则称v为G的一个割点(cut-vertex)。即去掉一个顶点(及其相关联边)后，分支数增加v1,v2是割点w(G)表示图G的分支个数割边定理定理3.1.1边e是G的割边当且仅当e不在G的任何圈中证明：(1)设e是

2、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相连接。于是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就在

3、G的圈P+e中。割点定理(1)定理3.1.2当且仅当在G中存在与顶点v不同的两个顶点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中不能有一

4、条联结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也不是割点。割点定理(3)定理3.1.4树G中所有度大于1的顶点都是割点。证明：(1)若d(v)=0，v显然不是割点；(2)若d(v)=1，则G-v的边数比顶点数少1，且无

5、圈，所以G-v仍是一棵树，因而G-v是连通的，故v不是割点；(3)若d(v)>1，则存在与v邻接的不同顶点u和w。道路uvw是G唯一一条(u,w)道路，于是去掉v后，G-v没有(u,w)道路，因为G-v是分离图，故v是割点。不可分图没有割点的非平凡的连通图称为不可分图(nonseparablegraph)。定理3.1.5不可分图的任一边至少在一个圈中。证明：设e是不可分图G的任意边，e=(x,y)，x和y都不是割点，所以图G-e是连通的，故G-e必有一条(x,y)道路P。于是P+e就是构成G中的一个圈。第三章：图的连通性

6、割边和割点点割集和边割集边连通和点连通连通度点割集定义：对于图G，若V(G)的子集V′使得w(G−V′)>w(G)，则称V′为图G的顶点割集。含有k个顶点的点割集称为k-点割集割点是1-点割集。完全图没有点割集。边割集定义：对于图G，若E(G)的子集E′使得w(G−E′)>w(G)，则称E′为图G的边割集。含有k条边的边割集称为k-边割集一条割边构成一个1-边割集对于非平凡图G，若E′是一个边割集，则GE不′连通。(点)连通度连通度κ(G)=min{

7、V′V′是G的顶点割集}完全图的连通度定义为κ(K)

8、=v−1。v空图的连通度定义为0。直观上看，右边的比左边的图连通“程度”要好。(点)连通度图的(点)连通度我们常常省略“点”字称连通度。树是具有最小连通度的图。若κ(G)≥k，则称G是k-连通的。若G是平凡图或非连通图，则κ(G)=0。所有非平凡连通图都是1连通的。边连通度边连通度λ(G)=min{

9、SS是G的边割集}完全图的边连通度定义为λ(K)=v−1。v空图的边连通度定义为0。边连通度λ(G)有时又记作κ′(G)。边连通度若G是平凡图或非连通图，则λ(G)=0。若G是含有割边的连通图，则λ(G)=1

10、。若λ(G)≥k，则称G是k-边连通的。所有非平凡连通图都是1-边连通的。连通度定理定理3.2.1κ(G)≤λ(G)≤δ(G)，其中δ(G)是图G的顶点的最小度。证明：先证κ(G)≤λ(G)若G不连通，则κ(G)=λ(G)=0若G是完全图，