图的连通性和14.4图的矩阵表

《图的连通性和14.4图的矩阵表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、14.2通路、回路通路与回路是图论中两个重要而又基本的概念本节所述定义一般说来既适合无向图，也适合有向图，否则将加以说明或分开定义。1定义14.11（通路、回路）给定图G，设G中顶点和边的交替序列Г=v0e1v1e2…vi-1eivi…envn若Г满足：对于i=1,2,…n，vi-1和vi是ei的端点（在G是有向图时，要求vi-1是ei的始点，vi是ei的终点），则称Г为从v0到vn的一条通路或链（chain）。v0和vn分别称为此通路的起点和终点。Г中边的数目n称为通路的长度(length)当v0=vn时，此通路称为回路（circuit）说明（1）可以用边

2、的序列Г=e1e2…en表示通路或回路（2）在简单图中，可以只用顶点Г=v0v1…vn表示通路或回路2有边重复出现的通路称为复杂通路；有边重复出现的回路称为复杂回路。若通路中无边重复，则称该通路为简单通路；无边重复的回路称为简单回路。若通路中无边重复且无顶点重复，则称该通路为初级通路或路径（path）；无边重复且无顶点重复的回路称为初级回路或圈（cycle）。将长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈。易见（1）初级通路(回路)是简单通路(回路)，但反之不真。（2）通路、回路是图的子图。3注意（1）在无向图中，环和平行边构成的回路分别是长度为1和2的初

3、级回路（圈）。（2）在有向图中，环和两条方向相反边（对称边）构成的回路分别是长度为1和2的初级回路（圈）。思考：在简单无(有)向图中，圈的长度至少为多长？在简单无向图中，圈的长度至少为3在简单有向图中，圈的长度至少为24通路、回路的性质定理14.5在一个n阶图中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n-1的通路。推论在一个n阶图中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于等于n-1的初级通路。定理14.6在一个n阶图中，若存在vi到自身的回路，则从vi到自身存在长度小于等于n的回路。推论在一个n

4、阶图中，若存在vi到自身的简单回路，则从vi到自身存在长度小于等于n的初级回路。514.3图的连通性6首先讨论无向图的连通性。定义14.12（连通）在一个无向图G=中，如果顶点u，v之间存在通路，则称u，v是连通的（connected），记作uv。vV，规定vv。由连通的定义可以定义如下的无向图中顶点之间的连通关系:={

5、u,vV∧u与v之间有通路}显然是自反的、对称的、传递的，所以是V上的等价关系。7定义14.13（无向连通图）若无向图G是平凡图或G中的任何两个顶点都是连通的，则称G是连通图（connectedgraph

6、），否则称G为非连通图或分离图（disconnectedgraph）。例：完全图Kn（n1）为连通图，零图Nn（n2）都是分离图。8定义14.14（连通分支）设无向图G=，V关于顶点之间的连通关系的商集V/={V1,V2,…,Vk}，Vi为等价类，称Vi的导出子图G[Vi]（i=1,2,…,k）为G的连通分支（connectedcomponent），连通分支数k常记为p(G)。或若无向图G由若干彼此不连通的子图组成，而每个子图是连通的，称这些子图为G的连通分支。显然若G为连通图，则p(G)=1；若G为非连通图，则p(G)2；Nn（n2）

7、的连通分支为p(G)=n9思考题（1）n阶非连通的简单图的边数最多有多少条？最少呢？P289/P292-6(2)（2）证明：若无向图G中恰有两个奇度顶点，这两个奇度顶点必然连通。P291/P293-3910下面讨论有向图的连通性定义14.20在一个有向图D=中，如果顶点u，v之间存在通路，则称u可达v，记作u→v。规定任意的顶点总是可达自身的，即uV，u→u。若u→v且v→u，则称u与v是相互可达的，记作uv，规定uu。11有向图有三种不同类型的连通图定义14.22（弱、单向、强连通图）在一个有向图D中，如果D的基图是连通图，则称D是弱连通

8、图(weaklyconnectedgraph)。如果对于任意的两个顶点u，v，u→v与v→u至少成立其一，则称D是单向连通图（unilateralconnectedgraph）。如果对于任意的两个顶点u，v，均有uv，则称D是强连通图（stronglyconnectedgraph）。说明：强连通图一定是单向连通图，单向连通图一定是弱连通图。12强连通图和单向连通图的判别定理定理14.8有向图D是强连通图当且仅当D中存在经过每个顶点至少一次的回路。定理14.9有向图D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。13例（1）（2）（3）（1）是强连

9、通图（2）是单向连通图（3）是弱连通图1414.4图