算法设计与分析 第三章 图与遍历算法.doc

第三章图与遍历算法§1 图的基本概念和术语?无向图(undirected graph) 哥尼斯堡七桥 Euler 图无向图,简称图,是一个用线(边)连接在一起的节点(顶点)的集合。严格地说,图是一个三元组 G=( V,E,I), 其中, V 是顶点的集合, E 是边的集合,而 I 是关联关系,它指明了 E 中的每条边与 V 中的每个顶点之间的关联关系:每条边必定连接两个而且只有两个顶点,它们称为该边的端点。连接顶点 v 的边的条数称为 v的度,记做 d(v). 图G=( V,E,I)中顶点的度与边数有如下关系||2)(Evd Vv???( ) 由公式( 1)可知, 图中奇度顶点的个数一定是偶数。没有重边的图称为简单图, n 阶完全图是指具有 n 个顶点而且每两个顶点之间都有边连接的简单图,这样的图的边数为 n(n-1)/2. 以下是 1-4阶的完全图: 另一类特殊的图是偶图(也叫二分图) ,它的顶点集分成两部分 V 1,V 2 ,同一部分的顶点之间不相连(没有边连接)。一个偶图设图 G 的顶点集是 V={v 1,v 2,…,v n} ,边集是 E={e 1,e 2,…,e m} ,则顶点与顶点之间的邻接关系、顶点与边之间的邻接关系可以列表如下: v 1v 2…v nv 1a 11a 12…a 1n邻接矩阵 v 2a 21a 22…a 2nA=(a ij) n×n 。。。…。。。。…。。。。…。 v na n1a n2…a nn 其中???? otherwise adjacent are vand v ifa ji ij0 1 e 1e 2…e mv 1c 11c 12…c 1m关联矩阵 v 2c 21c 22…c 2mM=(c ij) n×m 。。。…。。。。…。。。。…。 v nc n1c n2…c nm K 1 K 4 K 3K 2V 1V 2 其中???? otherwise eofpo end the ofone isv ifc ji ij0 1ints 图 3-1-1 一个具有 7 5个顶点的图图3-1 的邻接矩阵为 A ,关联矩阵是 M :???????????????????0110000 1010000 1101000 0010000 0000001 0000001 0000110A???????????????????1100000 1010000 0111000 0001000 0000110 0000011 0000101M 图的另一个重要概念是路径,途径、迹、路。途径:顶点与边交叉出现的序列 v 0e 1v 1e 2v 2··· e lv l() 其中 e i的端点是 v i-1和v i。迹是指边不重复的途径,而顶点不重复的途径称为路。路是要求最严的。一条途径: v 1e 1v 2e 10v 4e 5v 3e 9v 1e 1v 2e 2v 8一条迹: v 1e 1v 2e 10v 4e 5v 3e 9v 1e 4v 7一条路: v 1e 1v 2e 10v 4e 5v 3e 8v 5e 12v 7 图 3-1-2 立方体 H 起点和终点重合的途径称为闭途径,起点和终点重合的迹称为闭迹,顶点不 V 1V 2V 3V 4V 5V 6V 7V 8 e 1e 2e 3 e 5e 6e 7e 8e 9e 10e 11 e 12e 4 e 5e 6e 7e 46 457 e 11e 2e 33 2 重复的闭迹称为圈。没有圈的图称为森林。如果存在一条以 u为起点、v为终点的途径,则说顶点 u可达顶点 v。如果图 G中任何两个顶点之间都是可达的,则说图 G是连通。如果图 G不是连通的,则其必能分成几个连通分支。图3-2 是连通的,而图 3-1 不是连通的,它有两个连通分支。不含圈的连通图称为树,森林的连通分支是树,也就是说,森林是由树组成的。森林即是不含圈的图。适当去掉连通图中的一些边后,会得到一个不含圈、而且包含所有顶点的连通图,它是一棵树,称为原图的生成树。生成树是其所在的图中边数最少的连通生成子图,因此,具有 n 个顶点的连通图的边数至少是 n-1 . 不连通图没有生成树,但有生成森林。如果不连通图 G有k 个连通分支, 则G的边数至少是 n-k. 定理 如果 G是具有 n个顶点、 m条边的图,下列结论成立: , 则m=n-1 ; ,而且满足 m=n-1 ,则 G是树; ,而且满足 m=n-1 ,则 G是树; k棵树构成的森林,则 m=n-k ; ,而且满足 m=n-k ,则 G是森林。?有向图图 3-1-3 一个有向图及其双向连通分支 23 4 56 1 单向单向单向单向街道 1街道 3街道 2 大街