中科院陈玉福算法讲义ch2.pdf

中科院陈玉福算法讲义ch2.pdf

ID:52521166

大小:317.72 KB

页数:28页

时间:2020-03-28

中科院陈玉福算法讲义ch2.pdf_第1页
中科院陈玉福算法讲义ch2.pdf_第2页
中科院陈玉福算法讲义ch2.pdf_第3页
中科院陈玉福算法讲义ch2.pdf_第4页
中科院陈玉福算法讲义ch2.pdf_第5页
资源描述:

《中科院陈玉福算法讲义ch2.pdf》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第二章图与遍历算法19第二章图与遍历算法§1图的基本概念和术语ò无向图(undirectedgraph)图2-1-1哥尼斯堡七桥图2-1-2Euler图无向图,简称图,是一个用线(边)连接在一起的节点(顶点)的集合。严格地说,图是一个三元组G=(V,E,I),其中,V是顶点的集合,E是边的集合,而I是关联关系,它指明了E中的每条边与V中的每个顶点之间的关联关系:每条边必定连接两个而且只有两个顶点,它们称为该边的端点。有边相连的两个顶点称为相邻的。连接顶点v的边的条数称为v的度,记做d(v).图G=

2、(V,E,I)中顶点的度与边数有如下的Euler公式∑d(v)=

3、2E

4、(2.1.1)v∈V由公式(2.1.1)可知,图中奇度顶点的个数一定是偶数。没有重复边的图称为简单图,n阶完全图是指具有n个顶点而且每两个顶点之间都有边连接的简单图,这样的图的边数为n(n-1)/2.以下是1~4阶的完全图:20第二章图与遍历算法K2K4K1K3图2-1-3几个完全图另一类特殊的图是偶图(也叫二部图),它的顶点集分成两部分V1,V2,每部分中的顶点之间不相连(没有边连接)。V1V2图2-1-4一个偶图当然,k-

5、部图,是指图的顶点集被分成k个部分,同部分的顶点之间没有边相连。设图G的顶点集是V={v,v,L,v},边集是E={e,e,L,e},则顶点与顶12n12m点之间的邻接关系可以用如下矩阵表示:vvLv12nv1⎛a11a12La1n⎞⎜⎟v2⎜a21a22La2n⎟=A⎜⎟MLLLL⎜⎟⎜⎟vaaLan⎝n1n2nn⎠称为邻接矩阵,其中⎧1(如果vv,)是的一条边Gija=⎨ij⎩0否则顶点与边之间的关联关系可以用如下矩阵表示:第二章图与遍历算法21eeLe12mv1⎛b11b12Lb1m⎞⎜⎟v

6、2⎜b21b22Lb2m⎟=M⎜⎟MLLLL⎜⎟⎜⎟vbbLbn⎝n1n1nm⎠称为关联矩阵,其中⎧1如果ve是边的一个端点ijb=⎨ij⎩0否则41e4图2-1-5一个具有7e1e35个定点、7条e5e6边的图2e7e2367图2-1-5的邻接矩阵A、关联矩阵M分别为:⎡0110000⎤⎡1010000⎤⎢⎥⎢⎥10100001100000⎢⎥⎢⎥⎢1100000⎥⎢0110000⎥⎢⎥⎢⎥A=⎢0000100⎥M=⎢0001000⎥⎢0001011⎥⎢0001110⎥⎢⎥⎢⎥⎢0000101⎥

7、⎢0000101⎥⎢⎣0000110⎥⎦⎢⎣0000011⎥⎦图的另一个重要概念是路径,区分为途径、迹和路。途径:顶点与边交叉出现的序列v0e1v1e2v2···elvl(2.1.2)其中ei的端点是vi-1和vi。迹是指边不重复的途径,而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径,起点和终点重合的迹称为闭迹,顶点不重复的闭迹称为圈。没有圈的图称为森林。如果存在一条以u为起点、v为终点的途径,则说顶点u可达顶点v。如果图G中任何两个顶点之间都是可达的,则说图G是连通的。如果图G不是连通

8、的,则其必能分成几个连通分支。图2-1-6是连通的,而图2-1-5不是连通的,它有22第二章图与遍历算法两个连通分支。V1eV21一条途径:ve9V3e5V4e101e1v2e10v4e5v3e9v1e1v2e2v8e2一条迹:e8e6e4vV1e1v2e10v4e5v3e9v1e4v75V6一条路:e7e12e11v1e1v2e10v4e5v3e8v5e12v7V7e3V8图2-1-6立方体不含圈的连通图称为树。森林的每个连通分支都是树,也就是说,森林是由树组成的。对于连通图,适当去掉一些边后(

9、包括去掉零条边),会得到一个不含圈、而且包含所有顶点的连通图,它是一棵树,称为原图的生成树。一棵具有个顶点的树的边数恰好为nn−1。所以,一个具有个连通分支的森林恰好有kn−k条边。一个具有n个顶点的连通图至少有n-1条边;一个具有个顶点,nk个连通分支的图至少有n−k条边.定理2.1.1如果G是具有n个顶点、m条边的图,则下列结论成立:1.若G是树,则m=n-1;2.若G是连通图,而且满足m=n-1,则G是树;3.若G不包含圈,而且满足m=n-1,则G是树;4.若G是由k棵树构成的森林,则m=n

10、-k;5.若G有k个连通分支,而且满足m=n-k,则G是森林。由图G的部分顶点和部分边按照它们在G中的关联关系构成的图称为G的子图,如果子图H的顶点集恰是G的顶点集,则H称为G的生成子图。可见,当G是连通图时,它的生成树是一种特殊的生成子图,它是G的既连通又边数最少的一个生成子图。一个连通图的生成树不是唯一的。ò有向图描述单行道系统就不能用无向图,因为它不能指明各条路的方向。所谓有向图实际上是在无向图的基础上进一步指定各条边的方向。在有向图中每一条有向边可以用一对顶点表示:e=(u

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。