第三章图与遍历算法 §1图的基本概念和术语 ●无向图( undirected graph) 哥尼斯堡七桥 Euler 图 无向图,简称图,是一个用线(边)连接在一起的节点(顶点)的集合。严 格地说,图是一个三元组G=(V,E,I),其中,V是顶点的集合,E是边的集 合,而I是关联关系,它指明了E中的每条边与V中的每个顶点之间的关联关 系:每条边必定连接两个而且只有两个顶点,它们称为该边的端点。连接顶点v 的边的条数称为v的度,记做d(v).图G=(V,E,I)中顶点的度与边数有如下 关系 ∑d(v)=2|E (3.1.1) 由公式(1)可知,图中奇度顶点的个数一定是偶数。 没有重边的图称为简单图,n阶完全图是指具有n个顶点而且每两个顶点之 间都有边连接的简单图,这样的图的边数为n(n-1)/2.以下是1-4阶的完全图
第三章 图与遍历算法 §1 图的基本概念和术语 z 无向图(undirected graph) 哥尼斯堡七桥 Euler 图 无向图，简称图，是一个用线（边）连接在一起的节点（顶点）的集合。严 格地说，图是一个三元组 G=( V, E, I ), 其中，V 是顶点的集合，E 是边的集 合，而 I 是关联关系，它指明了 E 中的每条边与 V 中的每个顶点之间的关联关 系：每条边必定连接两个而且只有两个顶点，它们称为该边的端点。连接顶点 v 的边的条数称为 v 的度，记做 d(v). 图 G=( V, E, I )中顶点的度与边数有如下 关系 d(v) 2 | E | v V ∑ = ∈ （3.1.1） 由公式（1）可知，图中奇度顶点的个数一定是偶数。 没有重边的图称为简单图，n 阶完全图是指具有 n 个顶点而且每两个顶点之 间都有边连接的简单图，这样的图的边数为 n(n-1)/2.以下是 1－4 阶的完全图：
另一类特殊的图是偶图(也叫二分图),它的顶点集分成两部分V1,V2,同 一部分的顶点之间不相连(没有边连接)。 一个偶图 设图G的顶点集是v={v,V2,…,w},边集是E={e,e2,…,ea},则顶点 与顶点之间的邻接关系、顶点与边之间的邻接关系可以列表如下 anan2·an 邻接矩阵 a if vi and v i are adjacent 其中aj-10 otherwise 关联矩阵 M(ciinxa
另一类特殊的图是偶图（也叫二分图），它的顶点集分成两部分 V1，V2，同 一部分的顶点之间不相连（没有边连接）。 一个偶图 设图 G 的顶点集是 V={v1, v2, …,vn}，边集是 E={e1, e2, …,em}，则顶点 与顶点之间的邻接关系、顶点与边之间的邻接关系可以列表如下： v1 v2 … vn v1 a11 a12 … a1n 邻接矩阵 v2 a21 a22 … a2n A=(aij)n×n 。 。 。 … 。 。 。 。 … 。 。 。 。 … 。 vn an1 an2 … ann 其中 = otherwise if v and v are adjacent a i j ij 0 1 e1 e2 … em v1 c11 c12 … c1m 关联矩阵 v2 c21 c22 … c2m M=(cij)n×m 。 。 。 … 。 。 。 。 … 。 。 。 。 … 。 vn cn1 cn2 … cnm K1 K4 K3 K2 V1 V2
其中C I if vi is one of the end points of o otherwise 图3-1 一个具有7 个顶点的图 7 图3-1的邻接矩阵为A,关联矩阵是M: 0110000 01000 1000000 10000 1000000 011000 A=0000100M=000100 00000 0001011 000111 0000 01 000010 0000110 000001 图的另一个重要概念是路径,途径、迹、路。 途径:顶点与边交叉出现的序列 Vo el vi e2 v2 其中e的端点是v1-1和v1。迹是指边不重复的途径,而顶点不重复的途径称为 路。路是要求最严的 条途径: 一条迹: V VIelvee10vaesv3e9v1e4V7 ov6 一条路: e12 图3-1-2立方体H 起点和终点重合的途径称为闭途径,起点和终点重合的迹称为闭迹,顶点不
其中 = otherwise if v is one of the end po of e c i j ij 0 1 ints 图 3-1-1 一个具有 7 5 个顶点的图 图 3-1 的邻接矩阵为 A，关联矩阵是M ： = 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 A = 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 M 图的另一个重要概念是路径，途径、迹、路。 途径：顶点与边交叉出现的序列 v0 e1 v1 e2 v2 ··· el vl (3.1.2) 其中 ei的端点是 vi－1和 vi 。 迹是指边不重复的途径，而顶点不重复的途径称为 路。路是要求最严的。 一条途径： v1e1v2e10v4e5v3e9v1e1v2e2v8 一条迹： v1e1v2e10v4e5v3e9v1e4v7 一条路： v1e1v2e10v4e5v3e8v5e12v7 图 3-1-2 立方体 H 起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不 V1 V2 V3 V4 V5 V6 V7 V8 e1 e2 e3 e5 e6 e7 e8 e9 e10 e12 e11 e4 e5 e6 e7 e4 6 4 5 7 e1 1 e2 e3 3 2
重复的闭迹称为圈。没有圈的图称为森林。如果存在一条以u为起点、V为终点 的途径,则说顶点u可达顶点va如果图G中任何两个顶点之间都是可达的,则 说图G是连通。如果图G不是连通的,则其必能分成几个连通分支。图3-2是连 通的,而图3-1不是连通的,它有两个连通分支。 不含圈的连通图称为树,森林的连通分支是树,也就是说,森林是由树组 成的。森林即是不含圈的图。适当去掉连通图中的一些边后,会得到一个不含圈 而且包含所有顶点的连通图,它是一棵树,称为原图的生成树。生成树是其所在 的图中边数最少的连通生成子图,因此,具有n个顶点的连通图的边数至少是 n-1.不连通图没有生成树,但有生成森林。如果不连通图G有k个连通分支 则G的边数至少是n-k 定理3.1.1如果G是具有n个顶点、m条边的图,下列结论成立 若G是树,则m=n-1 2.若G是连通图,而且满足m=n-1,则G是树; 3.若G不包含圈,而且满足m=n-1,则G是树; 4.若G是由k棵树构成的森林,则皿=n-k 5.若G有k个连通分支,而且满足m=n-k,则G是森林 有向图 街道1 街道2 街道3 大街 单向 大街2 单向 单向 单向 图3-1-3 个有向图及其 双向连通分支
重复的闭迹称为圈。没有圈的图称为森林。如果存在一条以 u 为起点、v 为终点 的途径，则说顶点 u 可达顶点 v。如果图 G 中任何两个顶点之间都是可达的，则 说图 G 是连通。如果图 G 不是连通的，则其必能分成几个连通分支。图 3-2 是连 通的，而图 3-1 不是连通的，它有两个连通分支。 不含圈的连通图称为树，森林的连通分支是树，也就是说，森林是由树组 成的。森林即是不含圈的图。适当去掉连通图中的一些边后，会得到一个不含圈、 而且包含所有顶点的连通图，它是一棵树，称为原图的生成树。生成树是其所在 的图中边数最少的连通生成子图，因此，具有 n 个顶点的连通图的边数至少是 n-1 .不连通图没有生成树，但有生成森林。如果不连通图 G 有 k 个连通分支， 则 G 的边数至少是 n-k. 定理 3.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 是森林。 z 有向图 图 3-1-3 一个有向图及其 双向连通分支 2 3 4 5 6 1 单向 单向 单向 单向 街道 1 街道 2 街道 3 大街 1 大街 2 2 3 4 5 6 1
描述单行道系统就不能用无向图,因为它不能指明各条路的方向。所谓有 向图实际上是在无向图的基础上进一步指定各条边的方向。在有向图中,顶点v 的出度是指由顶点v出发的有向边的条数,记做d(v);而入度则是指向顶点v 的有向边的条数,记做d(v)。此外也有顶点度的概念,它是该顶点的出度与入 度的和:d(v)=d+(v)+d(v)。 在有向图中,许多概念都可以通过无向图的相关概念加“有向”二字得到, 如有向边、有向途径、有向迹、有向路、有向圈,等等。有向图和无向图可以 相互转化:将一个无向图的每条边都规定方向后,即得到有向图,其称为原无向 图的一个定向图;将一个有向图的各条有向边的方向去掉,即得到一个无向图 其称为原有向图的基础图 有向图中也有一些概念不能由无向图通过简单地附加“有向”一词而得到 如,连通,有向图D说是连通的是指其基础图是连通的。如果D中任意两个顶点 都是可达的,则说有向图D是双向连通的(或叫强连通)。这里,顶点u可达顶 点v是指存在一条以u为起点、v为终点的有向路。这里的起点、终点不能互为 替换。有向图3-3就是连通的,但不是双向连通的,因为从任何顶点出发,都没 有到达顶点3的有向途径。不是双向连通的有向图可以分解成几个双向连通分 支。图3-3共有5个双向连通分支,分别用不同的颜色标出。 加权图与网络 般的加权图是指对图的每条边e赋予一个实数值W(e)。如架设连接各城 镇的交通路网,需考虑各段线路的修建费用;在运输网络中要考虑网络各段线路 的容量,等等。 图3-1-4一个交通路网 网络是一个这样的加权有向图,其指明了收点集和发点集,在图3-5中分别 用粉色和黄色标出。其余的顶点称为内点(绿色)
描述单行道系统就不能用无向图，因为它不能指明各条路的方向。所谓有 向图实际上是在无向图的基础上进一步指定各条边的方向。在有向图中，顶点 v 的出度是指由顶点 v 出发的有向边的条数，记做 d＋(v)；而入度则是指向顶点 v 的有向边的条数, 记做 d- (v)。此外也有顶点度的概念，它是该顶点的出度与入 度的和: d(v)=d＋(v)+d- (v)。 在有向图中，许多概念都可以通过无向图的相关概念加“有向”二字得到， 如 有向边、有向途径、有向迹、有向路、有向圈，等等。有向图和无向图可以 相互转化：将一个无向图的每条边都规定方向后，即得到有向图，其称为原无向 图的一个定向图；将一个有向图的各条有向边的方向去掉，即得到一个无向图， 其称为原有向图的基础图。 有向图中也有一些概念不能由无向图通过简单地附加“有向”一词而得到。 如，连通，有向图 D 说是连通的是指其基础图是连通的。如果 D 中任意两个顶点 都是可达的，则说有向图 D 是双向连通的（或叫强连通）。这里，顶点 u 可达顶 点 v 是指存在一条以 u 为起点、v 为终点的有向路。这里的起点、终点不能互为 替换。有向图 3-3 就是连通的，但不是双向连通的，因为从任何顶点出发，都没 有到达顶点 3 的有向途径。不是双向连通的有向图可以分解成几个双向连通分 支。图 3-3 共有 5 个双向连通分支，分别用不同的颜色标出。 z 加权图与网络 一般的加权图是指对图的每条边 e 赋予一个实数值 W(e)。如架设连接各城 镇的交通路网，需考虑各段线路的修建费用；在运输网络中要考虑网络各段线路 的容量，等等。 图 3-1－4 一个交通路网 网络是一个这样的加权有向图，其指明了收点集和发点集，在图 3-5 中分别 用粉色和黄色标出。其余的顶点称为内点（绿色）。 6 6 2 3 7 2 3 1 3 6 8 3