算法设计与分析讲义-中科院-陈玉福ch2

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

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

2、d(v)=

3、2E

4、（2.1.1）v∈V由公式(2.1.1)可知，图中奇度顶点的个数一定是偶数。没有重复边的图称为简单图，n阶完全图是指具有n个顶点而且每两个顶点之间都有边连接的简单图，这样的图的边数为n(n-1)/2.以下是1～4阶的完全图：19K2K4K1K3图2-1-3几个完全图另一类特殊的图是偶图（也叫二部图），它的顶点集分成两部分V1，V2，每部分中的顶点之间不相连（没有边连接）。V1V2图2-1-4一个偶图当然，k-部图，是指图的顶点集被分成k个部分，每部分中的顶点之间没有边相连。设图G的顶点集是V={v,v,L,v}，边

5、集是E={e,e,L,e}，则顶点与顶12n12m点之间的邻接关系可以用如下矩阵表示：vvLv12nv1⎛a11a12La1n⎞⎜⎟v2⎜a21a22La2n⎟=AM⎜LLLL⎟⎜⎟⎜⎟vaaLan⎝111111⎠称为邻接矩阵，其中⎧1如果(v,v)是G的一条边ijaij=⎨⎩0otherwise顶点与边之间的关联关系可以用如下矩阵表示：20eeLe12mv1⎛m11m12Lm1m⎞⎜⎟v2⎜m21m22Lm2m⎟=M⎜⎟MLLLL⎜⎟⎜⎟vmmLmn⎝n1n1nm⎠称为关联矩阵，其中⎧1如果v是边e的一个端点ijmij=⎨⎩0ot

6、herwise41e4图2-1-5一个具有7e1e35个定点、7条e5e6边的图2e7e2367图2-1-5的邻接矩阵A、关联矩阵M分别为：⎡0110000⎤⎡1010000⎤⎢⎥⎢⎥10000001100000⎢⎥⎢⎥⎢1000000⎥⎢0110000⎥⎢⎥⎢⎥A=⎢0000100⎥M=⎢0001000⎥⎢0001011⎥⎢0001110⎥⎢⎥⎢⎥⎢0000101⎥⎢0000101⎥⎢⎣0000110⎥⎦⎢⎣0000011⎥⎦图的另一个重要概念是路径，区分为途径、迹和路。途径：顶点与边交叉出现的序列v0e1v1e2v2···elv

7、l(2.1.2)其中ei的端点是vi－1和vi。迹是指边不重复的途径，而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不重复的闭迹称为圈。没有圈的图称为森林。如果存在一条以u为起点、v为终点的途径，则说顶点u可达顶点v。如果图G中任何两个顶点之间都是可达的，则说图G是连通的。如果图G不是连通的，则其必能分成几个连通分支。图2-1-6是连通的，而图2-1-5不是连通的，它有21两个连通分支。V1eV21一条途径：ve9V3e5V4e101e1v2e10v4e5v3e9v1e1v2e2v8e2一

8、条迹：e8e6e4vV5V1e1v2e10v4e5v3e9v1e4v76一条路：e7e12e11v1e1v2e10v4e5v3e8v5e12v7V7e3V8图2-1-6立方体不含圈的连通图称为树。森林的每个连通分支都是树，也就是说，森林是由树组成的。对于连通图，适当去掉一些边后（包括去掉零条边），会得到一个不含圈、而且包含所有顶点的连通图，它是一棵树，称为原图的生成树。一棵具有n个顶点的树的边数恰好为n−1。所以，一个具有个连通分支的森林恰好有kn−k条边。一个具有n个顶点的连通图至少有n-1条边；一个具有个顶点，nk个连通分支的图

9、至少有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-k；5．若G有k个连通分支，而且满足m=n-k，则G是森林。由图G的部分定点和部分边按照它们在G中的关联关系构成的图称为G的子图，如果子图H的顶点集恰是G的顶点集，则H称为G的生成子图。可见，当G是连通图时，它的生成树是一种特殊的生成子图，它是G的既连通又边数最少的一个生成子图。一个连通图的

10、生成树不是唯一的。ò有向图描述单行道系统就不能用无向图，因为它不能指明各条路的方向。所谓有向图实际上是在无向图的基础上进一步指定各条边的方向。在有向图中每一条有向边可以用一对顶点表示：e=(u,v)，u为始点，v为终点，这条边是由顶点