离散数学 图论-通路与回路.ppt

《离散数学 图论-通路与回路.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、通路与回路离散数学§14.2通路、回路1、通路1）定义：给定有向图D中的任何一个边序列L，如果其中的任何一条边的终点，都是继之出现的边(如果存在的话)的始点，则称这样的边的序列是图G的通路。若序列中首尾结点相同，则称L为回路。2）定义：有向图D中，边序列中的各条边全都是互不相同的通路，称为简单通路。（无重复边）3）定义：有向图D中，序列中的每一个结点仅出现一次的通路，称为初级通路若序列中首尾结点相同，则称通路为初级回路或圈。（无重复点）4）定义：序列中边的条数称为它的长度2、简单通路和初级通路的关系有

2、向图中的每一条初级通路，也都必定是简单通路。反之不成立回路也可分为简单回路和初级回路。3、通路的表示：可仅用通路中的边序列表示：e1e2…ek也可仅用通路中所经过的结点的序列表示：v1v2v3…vk4、性质：1）定理在n阶图D中，若从顶点vi到vj(vi≠vj)存在通路，则从vi到vj存在长度小于或等于(n—1)的通路若大于n-1，则存在相同节点（有回路），将回路删去可得2）在n阶图D中，若从顶点vi到vj存在通路，则vi到vj一定存在长度小于或等于n—1的初级通路(路径)3）定理在一个n阶图D中，若

3、存在vi到自身的回路，则一定存在vi到自身长度小于或等于n的回路．4）在一个n阶图D中，若存在vi到自身的简单回路，则一定存在长度小于或等于n的初级回路．以上概念均可用在无向图G中§14.3图的连通性一、无向图的连通性1、结点的连通：设无向图G＝，∀u,v∈V，若u，v之间存在通路，则称u,v是连通的，记作u～v，∀u∈V，规定u～u2、结点的连通关系是等价关系若定义：～＝{┃u，v∈V且u与v之间有通路}此关系是自反，对称的，传递的，因而～是V上的等价关系3、无向图的连通图定义1

4、4．13若无向图G是平凡图或G中任何两个顶点都是连通的，则称G为连通图，否则称G为非连通图或分离图4、结点之间的距离1）定义：设u，v为无向图G中任意两个顶点若u～v，称u，v之间长度最短的通路为u，v之间的短程线短程线的长度称为u，v之间的距离，记作d(u，v)当u，v不连通时，规定d(u，v)＝∞．2）无向图结点的距离有以下性质：1．d(u，v)≥0，u=u时，等号成立．2．具有对称性：d(u，v)＝d(v，u)．3．满足三角不等式：∀u,v，w∈V(G)，则d(u，v)+d(v，w)≥d(u，w

5、)二、有向图的连通性1、结点的可达性定义：设D＝为一个有向图．∀vi,vj∈V，若从vi到vj存在通路则称vi可达vj,记作vi→vj。规定vi总是可达自身的，即vi→vi．2、结点的相互可达若vi→vj且vj→vi则称vi与vj是相互可达的，记作:vi↔vj规定vi↔vi．3、结点的可达关系为V上的二元关系，但不是等价关系（不满足对称性）。相互可达关系为V上的二元关系，且是V上的等价关系．有向图中顶点之间的可达关系既无对称性，也无反对称性4、有向图中结点的距离定义：设D＝为有向图

6、∀vi,vj∈V，若vi→vj，称vi到vi长度最短的通路为vi到vj的短程线短程线的长度为vi到vj的距离，记作d注：该定义与无向图中顶点vi与vj之间的距离d(vi，vj)的区别：无对称性一般地：d≠d（可能d不存在）5、弱连通图、单向连通图和强连通图定义1设D＝{V，E)为一个有向图．若D的作为无向图是连通图，则称D是弱连通图，简称为连通图．定义2设D＝{V，E)为一个有向图，若∀vi,vj∈V,vi→vj与vj→vi至少成立其一，则称D是

7、单向连通图．若∀vi,vj∈V，均有vi↔vj，则称D是强连通图注：三种图的关系：强连通图一定是单向连通图，反之不成立单向连通图一定是弱连通图．反之不成立6、有关强连通图与单向连通图的判定（1）定理：设有向图D＝，V＝{v1，v2，…，vn}．D是强连通图当且仅当D中存在经过每个顶点至少一次的回路．(2)定理设D是n阶有向图D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路．例2．设有向图D是单向连通图，但不是强连通图，问在D中至少加几条边所得图D’就能成为强连通图?作业：P29216

8、、17、18、39、40（1、2）、43§14.4图的矩阵表示一、图的矩阵表示用矩阵表示图之前，必须将图的顶点或边标定成顺序，使其成为标定图1、无向图的关联矩阵1）定义14．24设无向图G＝，V＝{v1,v2,…，vn}。E={e1,e2,e3，…em}，令mij为顶点vi与边ej的关联次数，则称(mij)nxm为G的关联矩阵，记作M(G)．2）关联矩阵的性质:关联矩阵是n行（结点数）m列（边数）的矩阵(1）M(G)每列元素之和均为2，这正说明