离散数学--第7章+图论-2路与连通

《离散数学--第7章+图论-2路与连通》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第七章图论-1引言7.1图的基本概念7.2路与连通7.3图的矩阵表示7.4最短路径问题7.5图的匹配8.1Euler图和Hamilton图8.2树8.3生成树8.4平面图7.2路与连通内容：图的通路，回路，连通性。重点：1、通路，回路，简单通路，回路,初级通路，回路的定义2、图的连通性的概念3、短程线，距离的概念。7.2.1路1、路(回路)中顶点和边的交替序列——，其中(无向图)，或(有向图)，——始点，——终点，称为到的路。当时，为回路。7.2.1路2.简单通路、简单回路边不同简单通路(迹)：路中所有的边都不同简单回路(闭迹)：回路中所有的边都不同复杂通路(回路)：路（

2、回路）中有重复的边出现7.2.1路3.初级通路、初级回路初级（基本）通路，初级回路：点不同初级通路(路径)：路中所有的顶点互不相同初级回路(圈)：回路中所有的顶点互不相同初级通路(回路)简单通路(回路)，但反之不真。4、路，回路的长度——中边的数目。7.2.1路例1、(1)例1、(1)图(1)中，从的路有：到…………长度3长度6长度67.2.1路例1、(1)图(1)中，从的通路有：到…………初级通路简单通路复杂通路7.2.1路例1、(2)…………长度3长度4长度7图(2)中过)有：的回路(从到7.2.1路例1、(2)…………初级回路(圈)初级回路(圈)复杂回路图(2)中过

3、)有：的回路(从到7.2.1路5、图中最短的回路如图：无向图中，环构成的回路长为1，两平行边构成的回路长为2。有向图中，环构成的回路长为1，两条方向相反的边构成的回路长为2。7.2.1路6、性质定理：阶图中，若从顶点到存在路，则从到存在长度小于等于在一个的路。推论：阶图中，若从顶点到存在通路，则从到存在长度小于等于在一个的初级通路。证明思路：多于n-1条边的路中必有重复出现的结点，反复删去夹在两个重复结点之间的边之后，剩余的边数不会超过n-1条边。7.2.1路6、性质定理：阶图中，若到自身存在回路，则从到自身存在长度小于等于的回路。在一个推论：阶图中，若到自身存在一个简单

4、回路，则从到自身存在长度小于等于的初级回路。在一个由以上定理可知，在阶图中，任何一条初级通路的长度任何一条初级回路的长度7.2.2图的连通性7.2.2图的连通性1、连通，可达。无向图中，从到存在路，称到是连通的(双向)。有向图中，从到存在路，称可达(注意方向)。2、短程线，距离。短程线——连通或可达的两点间长度最短的路。距离——短程线的长度，记无向图有向图7.2.2图的连通性2、短程线，距离若之间无路(或不可达)，规定距离满足：(1)，时，等号成立。(2)若是无向图，还具有对称性，。7.2.2图的连通性3、无向图的连通。为连通图——是平凡图，或都是连通的。中任两点为非连通

5、图——中至少有两点不连通。例这里是连通图，是非连通图，仅有一个顶点的图我们也把它看成是连通图。7.2.2图的连通性3、无向图的连通连通图可以看成是只有一个连通分支的图，即。结点之间的连通性是结点集V上的等价关系，对应该等价关系，必可将作出一个划分，把V分成非空子集V1,V2,…,Vm,使得两个结点vj和vk是连通的，当且仅当它们属于同一个Vi。把子图G(V1),G(V2),…,G(Vm)称为图G的连通分支（connectedcomponents）,图G的连通分支数记为W(G)。如上例中图的连通分支个数就是27.2.2图的连通性4、有向图的连通——中任一对顶点都互相可达(双

6、向)——中任一对顶点至少一向可达——略去中有向边的方向后得到的无向图连通连通强连通单向连通弱连通强连通单向连通弱连通强连通单向连通7.2.2图的连通性例2单向连通弱连通非连通图7.2.2图的连通性5图与顶点之间的若干关系把度数为1的顶点称为悬挂点（pendantnodes）各顶点的度均相同的图称为正则图(regulargraph),各顶点度均为k的正则图称为k-正则图。删除结点：所谓在图中删除结点v，即是把v以及与v关联的边都删除。删除边：所谓在图中删除某条边，即是把该边删除。见P-282页的图7-2.2和图7-2.3。7.2.3图的连通度定义7-2.4设无向图G=

7、E>是连通图,若有结点集V1V,使图G中删除了V1的所有结点后,所得到的子图是不连通图,而删除了V1的任何真子集后,所得到的子图仍是连通图,则称V1是G的一个点割集(cut-setofnodes)。k(G)=min{

8、V1

9、

10、是G的点割集}称为图G的点连通度(node-connectivity)。v5v1v2v4v5v1v4点割集V1={v2}7.2.3图的连通度定义7-2.5设无向图G=是连通图,若有边集E1E，使图G中删除了E1的所有边后，所得到的子图是不连通图，而删除了E1的任何真子集后，所得到的子图仍是连