图论第九章 有向图.ppt

《图论第九章 有向图.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第九章有向图定义1一个有向图是一个称为点集的非空集合V(D)和一个称为边集的集合E(D)组成的二元组(V(D)，E(D))。记为D=(V(D)，E(D))，简记为D=(V，E)，其中V∩E=Φ，E中每个元素均与V中一对有序点对相对应(点对中的点允许相同)。V中的元素称为顶点或点，E中的元素称为有向边或弧，也简称边。一、有向图有向图中，若边e和有序点对相对应，则记e=，此时u称为e的始点或起点，v称为e的终点。2§9.1有向图及其连通性无向图G的定向图：将G中每条边uv改为有向边〈u,v〉或〈v,u〉，所得的有向图。一个有向图的基础图

2、唯一，而一个图的定向图不唯一。有向图D的基础图：将D中每条有向边〈u,v〉改为边uv，所得的无向图。例下图中，前两个为有向图，它们都是后一个的定向图。3定义2设v是有向图D的一个顶点，称D中以v为始(终)点的边的数目为v的出(入)度，记为d+(v)(d-(v))，称v的出度与入度之和为v的度，记为d(v)。例对右图所示有向图，有d+(a)=1，d-(a)=2，d(a)=3，d+(b)=1，d-(b)=2，d(b)=3ab定理1设D=（V,E）是一个有向图，则有4若n条有向边的起点和终点均相同，则这n条边称为n重边，n称为这些边的重数。重数大于1的边也称

3、为重边，重数等于1的边也称为单边。既无环又无重边的有向图称为简单有向图。定义3设D=（V,E）是一个标定有向图，其中设V={v1,v2,…,vn}，E={e1,e2,…,em}。(1)称矩阵A(D)=(aij)n×n为D的邻接矩阵，其中aij是以vi作为始点，vj作为终点的边的数目，1≤i≤n,1≤j≤n。(2)若D无环，称矩阵M(D)=(mij)n×m为D的关联矩阵，其中，1≤i≤n,1≤j≤m。5例对所示的两个有向图D1和D2，有v2e1v1e2e3e4v3e5v4D2邻接矩阵A(D)的所有元素之和等于边数；关联矩阵每一列恰有一个“1”和一个“-1

4、”，第i行的1的个数等于d+(vi)，-1的个数等于d-(vi)。v2v1v3v4D16二、有向图的连通性有向途径：指一个有限非空点边交替序列G=v0e1v1e2…ekvk，使得对1≤i≤k，边ei的始点为vi-1，终点为vi。顶点v0与vk分别称为G的起点与终点，k称为G的长。有向迹：边不相同的途径；有向路、有向闭途径(也称有向回路)和有向圈等概念可仿照路、闭迹、圈的定义类似地给出。若A为标定有向图D中的邻接矩阵，则An的第i行第j列的元素为D中从vi到vj的长为n的有向途径数目。定义4设u和v为有向图D中的两个顶点，若D中存在有向(u,v)路，则称

5、在D中u可达v，记为u→v，规定u→u。7“可达”作为有向图的顶点集合V上的关系，具有自反性和传递性，但不能保证有对称性，因此它不是V上的等价关系。若u→v，并且v→u，则称u和v可互达，记为uv。易知关系“”是D(V)上的一个等价关系。定义5设D=（V,E）为一个有向图，2.若对u,v∈V，或u→v，或v→u，则称D是单向连通的。1.若对u,v∈V，u与v可互达，则称D是强连通的。3.若D的基础图是连通的，则称D是弱连通的，简称连通。关系:强连通一定单向连通，单向连通一定弱连通。注：8D1，D2，D3强连通图:单向连通图:弱连通图:D1D2D

6、3例D1D1，D2定理2有向图D=（V,E）是强连通的，当且仅当D中存在含有所有顶点的有向回路。9证明：必要性：设V(D)=｛v1,v2,…,vn｝。由于D是强连通图，所以，对任意两点vi与vj,都存在(vi,vj)路，同时也存在(vj,vi)路。所以存在如下闭途径：v1→v2→…→vn→v1。这是一条包含D的所有顶点的回路。充分性：设C=v1→v2→…→vn→v1是包含D的所有顶点的一条回路。对于D的任意两点vi与vj(i

7、任意两点是强连通的，即D是强连通图。例判断下图是否为强连通图。561234该图是强连通的。这是因该图存在含有所有顶点的有向回路124651351。定义6设D’是有向图D=(V,E)的一个子图。如果D’是强连通的(单向连通的、弱连通的)，且D中不存在真包含D’的子图是强连通的(单向连通的、弱连通的)，则称D’是D的一个强连通分支(单向连通分支、弱连通分支)。10强连通分支：极大的强连通子图例求下图D的强连通分支、单向连通分支。613254879DD的强连通分支：{1}{2,3,9,8,4,7}{5}{6}324879D的单向连通分支就是D本身。11顶点间

8、的强连通关系是等价关系。该等价关系对应的等价类在有向图D中的导出子图必然是D的一个强连通分支。