图论课件--有向图VIP免费

下载本文档

阅读 119
下载 1
格式 ppt
大小 873 KB
约31页
2024-11-11 发布于河南
收藏
评论
点赞(0)
海报
举报

1/31页

2/31页

3/31页

在线预览已结束，请下载后查看完整版，加入VIP享文档下载特权

/31

文本预览下载提示常见问题

10.810.60.40.20xt00.511.5210.500.51n图论及其应用应用数学学院20.810.60.40.20xt00.511.5210.500.51n本次课主要内容(一)、有向图的概念与性质(二)、有向图的连通性有向图(三)、图的定向问题(四)、有向路与有向圈30.810.60.40.20xt00.511.5210.500.51n1、概念定义1一个有向图D是指一个三元组(V(D),E(D),фD)。其中，V(D)是非空的顶点集合，E(D)是不与V(D)相交的边集合，而фD是关联函数，它使D的每条边对应D的有序顶点对(不必相异)。如果e是D的一条边，而u与v是使得фD(u,v)=e的顶点，那么称e是由u连接到v，记为e=。同时，称u为e的弧尾(起点),v为e的弧头(终点)。(一)、有向图的概念与性质注：有向图可以简单地理解为“边有方向的图”。40.810.60.40.20xt00.511.5210.500.51n例如：有向图Dv4v3v2v1e2e1e4e3e6e5e7132,evvv3与v2分别是e1的起点与终点。定义2在一个有向图D中，具有相同起点和终点的边称为平行边。两点间平行边的条数称为该两点间的重数。例如，在上图中，e6与e7是平行边。50.810.60.40.20xt00.511.5210.500.51n定义3在一个有向图D中，如果没有有向环和平行边，则称该图为简单有向图。定义4设D是有向图，去掉D中边的方向后得到的无向图G，称为D的基础图。又若G是无向图，给G的每条边加上方向后得到的有向图D称为G的一个定向图。e3非简单有向图Dv4v3v2v1e2e1e4e6e5e7简单有向图Dv4v3v2v1e2e1e4e6e560.810.60.40.20xt00.511.5210.500.51n定义5设D是有向图，v是D中顶点。以v为始点的边的条数称为点v的出度，以v为端点的一个自环算1度。点v的出度记为d+(v);以v为终点的边的条数称为点v的入度，以v为端点的一个自环算1度。点v的入度记为d-(v);点v的出度与入度之和称为点v的度，记为d(v)。有向图Dv4v3v2v1e2e1e4e6e5e74()2dv4()2dv4()4dv70.810.60.40.20xt00.511.5210.500.51n例1一个简单图有多少个定向图？答：因为每条边有2种定向方式，所以共有2m(G)种定向。例2求证：G存在一个定向图D，使得对，有()vVD()()1dvdv证明：不失一般性，设G是连通图。G中奇度顶点个数必然为偶数个，将偶数个奇数度顶点配对，然后在每一对配对顶点间连一条边得到欧拉图G1。在G1中用Fluery算法求出G的一欧拉环游C,然后顺次地在C上标上方向，由此得到C的定向图C1。在C1中，去掉添加的边后，得到G的定向图D.显然：80.810.60.40.20xt00.511.5210.500.51n对，有()vVD()()1dvdv2、性质定理1设D=(V,E)是有向图，则：()()()()()vVDvVDdvdvmD证明：由出度与入度的定义立即可得上面等式。3、有向图的矩阵表示90.810.60.40.20xt00.511.5210.500.51nE=｛e1,e2,…,em｝(1)称A(D)=(aij)n×n是D的邻接矩阵，其中aij是vi为始点，vj为终点的边的条数，1≦i≦n,1≦j≦n。定义6设D=(V,E)是有向图，其中V=｛v1,v2,…,vn｝(2)若D无环。称矩阵M=(mij)n×m是D的关联矩阵，其中1,-1(1,1),0,.ijijijvemveinjm是的始点，，是边的终点，其它100.810.60.40.20xt00.511.5210.500.51n例1写出下面有向图D1的邻接阵和D2的关联阵。v4v3v2v1D1v4v3v2v1e1e4e3e2e5D2101000212()00000010AD21000011110()0110100011MD110.810.60.40.20xt00.511.5210.500.51n1、相关概念(二)、有向图的连通性(1)有向途径(闭途径)、迹(闭迹)和路(圈)上面概念与无向图中相关概念类似。(2)有向图中顶点间的连通性定义7设D=(V,E)是有向图，u与v是D中两个顶点。1)若D中存在一条(u，v)路，则称u可达v,记为u→v。规定u→u。2)若D中存在一条(u，v)路或(v,u)路，则称u与v是单向连通的。120.810.60.40.20xt00.511.5210.500.51n3)若D中存在一条(u，v)路和一条(v,u)路，则称u与v是双向连通的或强连通的。D1D2D3定义8设D=(V,E)是有向图。1)若D的基础图是连通的，称D是弱连通图；2)若D的中任意两点是单向连通的，称D是单向连通图；3)若D的中任意两点是双向连通的，称D是强连通图；130.810.60.40.20xt00.511.5210.500.51n在上面三图中，D1是强连通的...

1、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
3、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。

碎片内容

图论课件--有向图

20xt00

5210

51n图论及其应用应用数学学院20

20xt00

5210

51n本次课主要内容(一)、有向图的概念与性质(二)、有向图的连通性有向图(三)、图的定向问题(四)、有向路与有向圈30

20xt00

5210

51n1、概念定义1一个有向图D是指一个三元组(V(D),E(D),фD)

其中，V(D)是非空的顶点集合，E(D)是不与V(D)相交的边集合，而фD是关联函数，它使D的每条边对应D的有序顶点对(不必相异)

如果e是D的一条边，而u与v是使得фD(u,v)=e的顶点，那么称e是由u连接到v，记为e=

同时，称u为e的弧尾(起点),v为e的弧头(终点)

(一)、有向图的概念与性质注：有向图可以简单地理解为“边有方向的图”

20xt00

5210

51n例如：有向图Dv4v3v2v1e2e1e4e3e6e5e7132,evvv3与v2分别是e1的起点与终点

定义2在一个有向图D中，具有相同起点和终点的边称为平行边

两点间平行边的条数称为该两点间的重数

例如，在上图中，e6与e7是平行边

20xt00

5210

51n定义3在一个有向图D中，如果没有有向环和平行边，则称该图为简单有向图

定义4设D是有向图，去掉D中边的方向后得到的无向图G，称为D的基础图

又若G是无向图，给G的每条边加上方向后得到的有向图D称为G的一个定向图

e3非简单有向图Dv4v3v2v1e2e1e4e6e5e7简单有向图Dv4v3v2v1e2e1e4e6e560

20xt00

5210

51n定义5设D是有向图，v是D中顶

起跑线书城 + 关注: 实名认证
内容提供者

热爱教学事业，对互联网知识分享很感兴趣

收藏店铺进入空间

图论课件--有向图VIP免费

图论课件--有向图

您可能关注的文档

相关文档

热门下载

相关标签