1、第5章 图的基本概念第5章 图的基本概念5.1 无向图及有向图无向图及有向图5.2 通路、回路、图的连通性通路、回路、图的连通性5.3 图的矩阵表示图的矩阵表示5.4 图的运算图的运算5.5 图的应用图的应用 第5章 图的基本概念5.1 无向图及有向图无向图及有向图5.1.1 无向图无向图无序积无序积 设A,B 为两集合,称a,b|aA bB为 A 与B 的无序积,记作A&B。将无序对a,b记作(a,b)。定义定义5.1 一个无向图G 是一个二元组,即G=,其中:(1)V 是一个非空的集合,称为G 的顶点集,V 中元素称为顶点或结点;(2)E 是无序积E&E 的一个多重子集,称 E 为G 的边
2、集,E 中元素称为无向边或简称边。第5章 图的基本概念5.1.2 有向图有向图定义定义5.2 一个有向图D 是一个二元组,即D=,其中:(1)V 同无向图中的顶点集;(2)E 是笛卡尔积的多重子集,其元素称为有向边,简称边。第5章 图的基本概念例例5.1 给定无向图和有向图的图形如图5-1(a)和(b)所示,试写出各图的顶点集和边集。图5-1 无向图和有向图第5章 图的基本概念第5章 图的基本概念5.1.3 相关概念相关概念1.几种特殊的图几种特殊的图设G=为一无向图或有向图:(1)若V,E 都是有穷集合,则称G 是有限图。(2)若|V|=n,则称G 为n 阶图。(3)若E=,则称G 为零图。
3、特别地,若此时又有|V|=1,则称G 为平凡图。(4)若V=,则称图G 为空图。第5章 图的基本概念2.关联关联定义定义5.3 设ek=(vi,vj)为无向图G=中的一条边,称vi 和vj为ek的端点,ek 与vi(或vj)是彼此关联的。(1)无边关联的顶点称为孤立点;(2)若一条边所关联的两条边重合,则称此边为环;(3)ek 与vi(或vj)的关联次数可用于表达关联矩阵。第5章 图的基本概念3.相邻和邻接相邻和邻接定义定义5.4 设无向图G=,vi,vjV,ek,elE。(1)若存在一条边e以vi,vj 为端点,即e=(vi,vj),则称vi,vj是彼此相邻的,简称相邻的。(2)若ek,el
4、 至少有一个公共端点,则称ek,el 是彼此相邻的,简称相邻的。类似可对有向图进行定义,只是这时若ek=(vi,vj),除称vi,vj 是ek的端点外,还称vi是ek的始点,vj是ek的终点,vi 邻接到vj,vj邻接于vi。第5章 图的基本概念第5章 图的基本概念例例5.2 给定图5-2,试分别写出图(a)、(b)的最大度和最小度。图5-2 最大度和最小度第5章 图的基本概念第5章 图的基本概念5.1.4 平行边、平行边、重数、重数、多重图、多重图、简单图简单图定义定义5.6 在无向图中,关联一对顶点的无向边如果多于1条,称这些边为平行边。平行边的条数称为重数。在有向图中,关联一对顶点的有向
5、边如果多于1条,且它们的始点与终点相同,则称这些边为有向平行边,简称平行边。含平行边的图称为多重图。既不含平行边,也不含环的图称为简单图。第5章 图的基本概念例例5.3 观察图5-3,指出哪些图是简单图?哪些图是多重图?为什么?图5-3 简单图和多重图第5章 图的基本概念解解 据简单图和多重图的定义知:(a)、(c)是简单图,因为它们无环且不含平行边;(b)、(d)是多重图,因为(b)既有环又有平行边,(d)上边存在一对有向平行边。第5章 图的基本概念5.1.5-基本定理基本定理(握手定理握手定理)第5章 图的基本概念第5章 图的基本概念例例5.4 判断下列各度数列哪些是可图画的,哪些是可简单
6、图画的。(1)(3,3,3,3)(2)(3,3,3,2,2)(3)(5,4,3,2,2)(4)(5,5,5,5,5,1)解解 由可图画的充分必要条件知,除(2)的度数列和为奇数不可图画外,其余皆可图画。(3)不可简单图画,因为(G)=54,与(G)n-1矛盾;(4)不可简单图画,因为前五点的度数是5,意味着它们要与不相邻的每个顶点有关联,但最后一个顶点的度数为1,不能为前五点提供5度;(1)可简单图画,只需四点互连即可。第5章 图的基本概念5.1.6 无向完全图、无向完全图、有向完全图有向完全图定义定义5.7 设G=是n 阶无向简单图,若G 中任何顶点都与其余的n-1个顶点相邻,则称G 为n
7、阶无向完全图,记作 Kn。设D=为n 阶有向简单图,若对于任意的顶点u,vV(uv),既有有向边,又有,则称D 是n 阶有向完全图。设 D=为n 阶有向简单图,若D 的基图为n 阶无向完全图Kn,则称D 为n 阶竞赛图。注意注意 后文中 Kn 均指无向完全图。第5章 图的基本概念例例5.5-在图5-4中(a)为K4,(b)所示为K5,(c)所示为3阶有向完全图,(d)为4阶竞赛图。图5-4 完全图、竞赛图第5章 图的基本概念5.1.7 子图子图第5章 图的基本概念例例5.6 在图5-5中,若将(a)视作母图,则(b)是生成子图,(c)是由顶点集V1=v1,v2,v3,v5导出的子图,(d)是由
8、边集E1=e1,e4,e5导出的子图。同时(b)也是由边集E1=e1,e4,e5,e6导出的子图,但不是由顶点导出的子图,因为V2=v1,v2,v3,v5不是V 的真子集。图5-5-母图、生成子图、导出子图第5章 图的基本概念第5章 图的基本概念图5-6 补图第5章 图的基本概念5.1.9 图的同构图的同构第5章 图的基本概念例例5.7 试说明图5-7中(a)和(b)是同构的。图5-7 图的同构第5章 图的基本概念第5章 图的基本概念5.2 通路、通路、回路、回路、图的连通性图的连通性5.2.1 通路和回路通路和回路定义定义5.9 给定图G=,设G 中顶点和边的交替序列为第5章 图的基本概念若
9、 满足如下条件:(1)vi-1和vi 是ei 的端点(在G 是有向图时,要求vi-1是ei 的始点,vi 是ei 的终点),i=1,2,3,n,则称 为顶点v0 到vn 的通路。(2)v0 和vn 分别称为此通路的起点和终点,中边的数目n 称为 的长度。(3)当v0=vn 时,此通路称为回路。若 中的所有边e1,e2,en 互不相同,则称 为简单通路或一条迹。若回路中的所有边互不相同,则称此回路为简单回路或一条闭迹。第5章 图的基本概念若通路的所有顶点v0,v1,v2,vn 互不相同(从而所有边互不相同),则称此通路为初级通路或一条路径。若回路中,除v0=vn 外,其余顶点各不相同,所有边也各
10、不相同,则称此回路为初级回路或圈。有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路。注意注意 初级通路(回路)是简单通路(回路),但反之不真第5章 图的基本概念由于上文的定义繁多,表5-1中总结了通路、迹、路径、回路和圈的一些重要特征,以帮助读者理解。第5章 图的基本概念例例5.8 考虑图5-8中v1 到v6 的通路有哪些?举出三个即可,并说明它们的长度以及是哪种通路。图5-8 无向图的通路第5章 图的基本概念第5章 图的基本概念例例5.9 考虑图5-9中v2 到v2 的回路有哪些?举出三个即可,并说明它们是哪种回路。图5-9 有向图的通路第5章 图的基本概念第5章 图的基本概念
11、第5章 图的基本概念5.2.2 图的连通性图的连通性1.连通连通定义定义5.10 在无向图G 中,若从顶点vi 到vj 存在通路(当然从vj 到vi 也存在通路),则称vi 到vj 是连通的。规定vi 到自身总是连通的。在有向图D 中,若从顶点vi 到vj 存在通路,则称vi 可达vj。规定vi 到自身总是可达的。第5章 图的基本概念2.短程线短程线设vi,vj为无向图G 中的任意两点,若vi 与vj是连通的,则称vi与vj 之间长度最短的通路为vi与vj之间的短程线;短程线的长度称为vi与vj之间的距离,记作d(vi,vj)。设vi,vj为有向图D 中任意两点,若vi可达vj,则称从vi 到
12、vj 长度最短的通路为vi到vj的短程线;短程线的长度称为vi 到vj的距离,记作d。第5章 图的基本概念3.图的连通性图的连通性定义定义5.11 若无向图G 是平凡图,或G 中任意两顶点都是连通的,则称G 是连通图;否则,称G 是非连通图。定义定义5.12 设D 是一个有向图,如果略去D 中各有向边的方向后所得无向图G 是连通图,则称D 是连通图,或称D 是弱连通图。若D 中任意两顶点至少一个可达另一个,则称D 是单向连通图。若D 中任何一对顶点都是相互可达的,则称D 是强连通图。第5章 图的基本概念例例5.10 在图5-10中,据连通图的相关定义可知三图去掉有向边后的无向图都是连通的,所以
13、(a)、(b)、(c)至少都是弱连通的;(a)中a 到d 是不可达的且d 到a 也是不可达的,所以(a)只是弱连通的;(b)中有通路afedbc,但是c到其余各点皆不可达,所以(b)是单向连通的;(c)中存在回路afedcba,各点都是可达的,所以(c)是强连通的。第5章 图的基本概念图5-10 图的连通性第5章 图的基本概念5.2.3 割集割集1.点割集点割集定义定义5.13 设无向图G=,若存在顶点子集VV,使G 删除V(将V中顶点及其关联 的 边 都 删 除)后,所 得 子 图 G-V的 连 通 分 支 数 与 G 的 连 通 分 支 数 满 足p(G-V)p(G),而删除V的任何真子集
14、V后,p(G-V)=p(G),则称V为G 的一个点割集。若点割集中只有一个顶点v,则称v 为割点。第5章 图的基本概念2.边割集边割集定义定义5.13(续)若存在边集子集EE,使G 删除E(将E中的边从G 中全删除)后,所得子图的连通分支数与G 的连通分支数满足p(G-E)p(G),而删除E的任何真子集E后,p(G-E)=p(G),则称E是G 的一个边割集。若边割集中只有一条边e,则称e为割边或桥。第5章 图的基本概念例例5.11 考虑图5-11,找出图中所有的边割集和点割集。图5-11 边割集和点割集第5章 图的基本概念第5章 图的基本概念5.3 图的矩阵表示图的矩阵表示5.3.1 无向图的
15、关联矩阵无向图的关联矩阵第5章 图的基本概念第5章 图的基本概念第5章 图的基本概念5.3.2 有向图的关联矩阵有向图的关联矩阵第5章 图的基本概念试观察关联矩阵中元素mij,不难发现有以下性质:第5章 图的基本概念图5-13 有向图第5章 图的基本概念5.3.3 有向图的邻接矩阵有向图的邻接矩阵1.表示法表示法设有向图D=,V=v1,v2,vn,E=e1,e2,em。令ai(j1)为vi 邻接到vj 的边数,称(ai(j1)nn为D 的邻接矩阵,记作A(D)。第5章 图的基本概念图5-14 有向图第5章 图的基本概念第5章 图的基本概念第5章 图的基本概念第5章 图的基本概念5.3.4 有向
16、图的可达矩阵有向图的可达矩阵第5章 图的基本概念5.4 图图 的的 运运 算算第5章 图的基本概念第5章 图的基本概念例例5.16 G1、G2 分别如图5-15(a)、(b)所示,G1+G2 如图5-15(c)所示。图5-15-两个图的和第5章 图的基本概念第5章 图的基本概念图5-16 两个图的笛卡尔积第5章 图的基本概念5.5 图图 的的 应应 用用5.5.1 无向图的加权矩阵无向图的加权矩阵图论有诸多应用,如显示中国的各省市之间的高速公路、纵向和横向的高铁主动脉、航空路线、春节客流流向、化学里不同化合物的相关性等。连接两个顶点的边通常可以关联一个非负实数,称之为权(weight)。若图5
17、-17表示中国某地市周围的公路结构,则权可以表示两地之间的距离,抑或表示时间或花销,我们称这样的图为加权图(weightedgraph)。第5章 图的基本概念图5-17 加权图第5章 图的基本概念第5章 图的基本概念5.5.2 最短路径算法最短路径算法设G 是加权图,a,z 为图中顶点,P 为G 中从a 到z 的路径,L(P)为该路径上所有边权之和。在图G 中,从a 到z 的路径有很多种,我们的目标是寻找L(P)的最小值,即最短路径。一种方法是寻找a 到z 的所有可能路径,然后选择距离最短的路径,随着顶点数的增加,这种方法极其耗费时间,所以本节考虑 Dijkstra最短路径算法,也称贪婪算法。
18、此外,本节只考虑正实数的权。第5章 图的基本概念Dijkstra最短路径算法基本思想:如果avi1vi2vikz 是a 到z 的最短路径,则对每个t(1tk),avi1vi2vit是a 到vit的最短路径。于是可设置并逐步扩充一个集合S,存放已求出最短路径的顶点,设尚未确定最短路径的顶点集合为 N=V-S,其中V 是图中所有顶点的集合。按最短路径长度递增的顺序逐个扫描集合 N 中元素,并加入集合S,直到S 包含全部顶点,而 N 变为空集。第5章 图的基本概念第5章 图的基本概念下面用该算法求图5-17中v1 到v7 的最短路径。已找到最短路径的点用圆圈圈起。(1)初始化后(即执行前 2 步后)
19、图 G、集合 S 与 N 和各顶点的标记值如图 5-18所示。(2)现考虑从第3步开始的第一次迭代。由3.a,3.b,3.c知,因为v1N 且L(v1)=minL(u)|uN,所以v1 被选中,且有S=v1,N=v2,v3,v4,v5,v6,v7。与v1 相邻的点有v2,v3,v4,于是,第一次迭代后图G、集合S 与N 和各顶点的标记值如图5-19所示。第5章 图的基本概念图5-18 初始化后图G、集合S 与N 和各顶点标记值第5章 图的基本概念图5-19 第一次迭代后图G、集合S 与N 和各顶点标记值第5章 图的基本概念第5章 图的基本概念图5-20 第二次迭代后图G、集合S 与N 和各顶点标记值第5章 图的基本概念第5章 图的基本概念图5-21 第三次迭代后图G、集合S 与N 和各顶点标记值第5章 图的基本概念第5章 图的基本概念图5-22 第四次迭代后图G、集合S 与N 和各顶点标记值第5章 图的基本概念第5章 图的基本概念图5-23 第五次迭代后图G、集合S 与N 和各顶点标记值第5章 图的基本概念图5-24 第六次迭代后图G、集合S 与N 和各顶点标记值
