第八章图论

《第八章图论》由会员分享，可在线阅读，更多相关《第八章图论（85页珍藏版）》请在金锄头文库上搜索。

1、第8章 图论,图论是建立和处理离散数学模型的 重要工具,是一门应用性很强的学科。 本章主要介绍图论的一些基本概念和 基本性质,然后介绍几种在实际应用中 有重要意义的特殊图。,8.1 基本概念,图在现实生活中随处可见，如交通运输图、旅游图、流程图等。此处我们只考虑由点和线所组成的图。这种图能够描述现实世界的很多事情。例如，用点表示球队，两队之间的连线代表二者之间进行比赛，这样，各支球队的比赛情况就可以用一个图清楚地表示出来。,定义 一个图G是一个有序二元组(V,E), 记作G=(V,E), 其中: (1) V=v1,v2,vn,是一个有限非空的集合, V的元素称为G的结点 (或顶点), V称为G

2、的结点集。 (2) E=(vi1,vi2),(vik-1 , vik ), 是V中不同元素的非有序对偶的集合, 这些对偶称为G的边(或弧), 而E称为G的边集。,一、图的定义,1. 无向图的定义,定义 设G=(V,E), V是一个有限非空集合, E是V中不同元素的有序对偶的集合, 则称G是一有向图。在有向图G中 若vivj,则(vi,vj)和(vj,vi)表示两条 不同的边,且用一个从结点vi指向vj 的箭头表示边(vi,vj)。,定义 具有n个结点和m条边的图称为(n,m)图。 (n,0)图称为零图。(1,0)图称为平凡图。,2. 有向图的定义,定义 如果边e=vi,vj是G的边, 则称结点

3、vi 和vj邻接的, 边e和结点vi ，边e和结点vj称为关联的。 没有与边关联的结点称为孤立点。 关联于同一结点的相异边称为邻接的。 不与任何边邻接的边称为孤立边。,3. 图的结点与边之间的关系,在上图中显然e1和e2, e1与e4是邻接的, 结点v1和v2,v2和v4等是邻接的, 没有孤立点和孤立边。,例1,定义 设G=(V,E),V是一个有限非空集, E是V中任意元素的非有序对偶的 多重集,则称G是一个伪图。 伪图与前面所定义的图的区别是: (1) E中允许出现相同元素的对偶, 即对于vV, 可能有v,vE。 v,v表示长为1的自回环。 (2) 对于元素vi和vj,E中无序对偶vi,vj

4、 可能出现r次, r1。边vi,vj称为多重边。,二、图的类型,1.伪图,2.多重图,没有长度为1的环的伪图。,3.简单图,既没有多重边，又没有长度为1的环。,4.有权图,每一条边都指定了权数。,有权图在实际生活中有着广泛的应用。 例如在城市交通运输图中, 可以赋予每条边 以公里数、耗油量、运货量等。 与此类似, 在表示输油管系统的图中, 每条边所指定的权表示单位时间内 流经输油管断面的石油数量。 如右边的图。,例2.如下图中: 图(a)是伪图。图(b)是有向多重 图。 最右第三个图是简单图有权图。,1.定义 图G中关联于结点vi的边的总数称为 结点vi的度, 用deg(vi)表示。,三、结点

5、的度,2.定理1(握手定理) 图G的所有结点的度的总和为边数 的二倍。即若G为具有n结点的(n,m)图, 则有：,例3 已知图G中有11 条边,1 个4 度的结点, 4 个3 度的结点, 其余结点的度数均不 大于2,问G中至少有几个结点？,解: 由握手定理, G中的各结点度数之和为22, 1个4度节点，4 个3 度结点共占去16 度, 还剩6度, 若其余结点全是2 度, 则还需要3 个结点, 所以至少1+4+3=8个结点。,例4 数列1,3,3,4,5,6,6 能否是一个 无向简单图的度数列?,解: 如果存在这样一个无向简单图, 那将它的一个6 度结点去掉, 得到的简单无向图的度数列为0,2,

6、2,3,4,5。 再将这一图的5 度结点去掉， 得到的简单图具有度数列0,1,1,2,3。 但这一图有3 个奇数度的结点, 这与定理2相矛盾。,3.定理2 在任何图中度数为奇数的结点个数 必为偶数。,定义 图G中l条边的序列 vi0,vi1,vi1,vi2, ,vil-1,vil称为 连接vi0到vil的长度为l的路。 若vi0vil,则称路vi0vi1vil为开路。 若vi0=vil,则称为回路。 若结点vi0 ,vi1 ,vil各不相同, 则称开路vi0vi1vil为真路。 若vi0 ,vi1 ,vil-1各不相同, 则称回路vi0 vi1 vil-1vi0为环。,四、 路与环,1. 路与

7、环的定义,定义 在图G中,从结点vi到vj若有一条或 更多条的路相连接, 则其中长度 最短的路,称其为从vi到vj的短程。 短程的长度称为两结点间的 距离。 记为d (vi, vj)。,定理 设G是有n个结点的图, 则对于任意 两个相连接的结点vi ， vj (vi vj) , 其短程是一条长度不大于n-1的真路。,推论 设G是具有n个结点的图, 则G中任一环的长度不大于n。,2. 两结点间的距离,定义 在图G中如果任意两个不同的结点 都是邻接的,则称图G是完全图。 n个结点的完全图记为 Kn。 显然完全图的边数为,五、完全图,如下图分别给出了1个、2个、3个、4个 和5个结点的完全图:,条。

8、,定义 图G的补图是由G的所有结点 和为了使G成为完全图所需要 添加的那些边所组成的图。,六、图的补图,如下图中, (a)与(b)互为补图,定义9 设有图G=(V,E)和G=(V,E), (1)若V V, E E, 则称G是G的子图。 (2)若V V, E E, 则称G是G的真子图。 (3)若V=V, E E, 则称G是G的生成子图,七、图的子图,如下图中(b),(c),(d)都是(a)的子图。,如下图所示,(b)(c)(d)都是(a)的子图,也是(a)真子图。,(b)和(c)都是(a)的生成子图。,定义 设G和G是两个分别具有结点集 V和 V的图, 若存在一个双射h:VV, 使得当且仅当vi

9、,vj是G中的边时, h(vi), h(vj)是G中的边, 则称G同构于G。,八、图的同构,说明 两个图同构的几个必要条件 (1) 结点数目相等； (2) 边数相等； (3) 度数相同的结点数目相等。,记为：,例5 判断下面两组图中(a)与(b)是否同构？ 为什么？,证明：对上图的G1和G2, 建立双射： h(a)=1,h(b)=3,h(c)=5, h(d)=2,h(e)=4,h(f)=6。 则G1和G2同构。,例6 证明下面两图同构,例7 设G=是简单无向图, 且#(V)=5,#(E)=3, 试画出G的所有不同构的图。,解: 5个结点,3条边的所有不同构的图如下：,定义 若图G中的任意两个结

10、点均是连接的, 则称图G是连通的,否则不连通 的。,九、图的连通性,定义 在图G中,若存在一条连接结点vi和vj的路, 则称这两个结点是连接的。, 图G中结点之间的连接关系可以看做是图G 的结点集V上的一个等价关系, 因此它的所有等价类构成V上的一个分划。 对于任意两个结点vi和vj， 若它们属于同一个等价类， 则它们有路连接, 反之,则没有任何路连接。,定义 将每一个等价类中的结点， 及与这些结点相关联的边所组成的 G的子图称为G的分图。,例8 如下图 (a)是连通图。 (b)是一个具有三个分图 的非连通图。,结论： (1)一个图的分图必是连通的； (2)一个连通图一定只能有一个分图。,例1

11、1 对于图的连通性，常常由于删除了 图中的结点和边而影响了图的连通性。,在连通图(a)中删除边e后, 则变成了不连通 的图(b)。,8.2 图的矩阵表示,前面讨论了图的图形表示方法以及相关的 性质, 在结点与边数不太多的情况下, 这种 表示方法有一定的优越性, 它比较直观明了, 但当图的结点和边数较多时, 就无法使用图 的图形表示法。由于矩阵在计算机中易于 储存和处理, 所以可以利用矩阵将图表示 在计算机中。,本节主要考虑3种矩阵：邻接矩阵、关联矩阵、 连接矩阵。,1. 定义 设图G=(V,E),其中V=v1,v2,vn, n 阶方阵A=(aij)称为G的邻接矩阵, 其中元素,一、邻接矩阵,例

12、1 求出下图的邻接矩阵A。,解: 该图的邻接矩阵,注: 一个无向图的邻接矩阵是对角线元素 均为0的对称0-1矩阵; 一个对角线元素均为零的对称0-1矩阵 一定可唯一地作出一个图G。,例2 有向图的邻接矩阵不一定为对称矩阵。,显然该矩阵是不对称的。,上图(a)的邻接矩阵为：,定理 设图G具有结点集v1,v2,vn, 图G的邻接矩阵为A, 则AL(L=1,2,3,)的(i, j)项元素a(L)ij 是连接vi到vj的长度为L的路的总数。,2.邻接矩阵的幂,例3 G=是简单有向图,写出G的邻接矩阵A, 算出A2,A3,并且确定出从v1到v2有几条长度 为3的路？ v1到v3有几条长度为2的路？,解:

13、,所以， v1 到v2 有2条长度为3的路， v1 到v3有1条长度为2的路。,定义 设图G有n个结点v1,v2,vn, m条边为 e1,e2,em, 则G的关联矩阵M(G)定义为M(G)=(mij), 其中:,二、关联矩阵,例4 写出下面图示中无向图的关联矩阵M。,解:,1. 定义 设图G=,其V=v1,v2,vn, n 阶方阵C=(cij)称为G的连接矩阵, 其中：,三、连接矩阵,（反映图的连通性）,2.求连接矩阵的方法：,且满足布尔运算。,3.结论：,若图的连接矩阵的所有元素全为“1”， 则此图是连通的。,例5 设有向图G的邻接矩阵A如下。 求连接矩阵C，并判定此图的连通性。,8.3 图

14、的连通性,定义1 如果在图G中删去边vi,vj后, 图G的分图数增加, 则称边vi,vj为G的割边。,定义 2 如果在图G中删去结点vi及 与其关联的所有边后, 图的分图数增加, 则称结点vi 是G的割点。,一、 割边、割点的定义,例1 在下图中, 结点c和结点e都是割点, 边e,c和e,f 都是割边。,定理1 在图G中, 边vi,vj为割边的充要条件是 边vi,vj不在G的任何环中出现。,二、割边、割点的判定,定理2 在图G中, 结点v为割点的充要条件是 存在两个结点u和w(uwv), 使得连接u和w的所有路中都出现结点 v。,定义3 设图G=是连通图,若有E的子集S, 使得在图G中删去了S

15、的所有边后, 得到的子图G-S变成具有两个分图的不连通图, 删去了S的任一真子集后所得子图仍是连通图， 则称S是G的一个边割集。 注：割边是边割集的一个特例。,三、边割集、点割集,定义4 设图G=(V,E)是连通图, 若有V的子集V1, 使得在图G中删去V1中的所有点后 所得到的子图G-V1不连通或为平凡图, 则称V1是G的一个点割集。 注: 割点是点割集的一个特例。,定义5 设图G=(V,E)是连通图,G中端点分别属于,所有边的集合，称为G的断集。,注：断集或是一个边割集， 或是某些边割集的不相交的并集。,定义6 设点v是图G=(V,E)的一个结点,与v相关联的所有边的集合，,称为结点v的关

16、联集，记为S(v).,定义7 设图G=(V,E)是一个连通图,是G的点割集,称为G的点连通度（或连通度）。,是G的断集,称为G的边连通度。,四、图的连通度,定理 对任意的图G=(V,E)，有,其中,是G中度最小的结点度数。,定义 设有图G=(V,E)，,若,则称G是h-连通的；,若,则称G是h-边连通的。,8.4 欧拉图和哈密顿图,1736年瑞士数学家欧拉发表了图论的第一篇 著名的论文“哥尼斯堡七桥问题”(下称七桥题)： 哥尼斯堡城有一条横贯全城的普雷格尔河, 河中有两个小岛, 城的各部分用七座桥连接, 每逢节假日, 有些城市居民进行环城周游, 于是便产生了能否“从某地出发, 通过每座桥 恰好一次, 在走遍七桥后又返回到出发点”的问题。 这个问题看起来简单, 但是谁也解决不了。 最终, 欧拉解决了这个问题, 第一