第2章第6节图论.ppt

《第2章第6节图论.ppt》由会员分享，可在线阅读，更多相关《第2章第6节图论.ppt（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,6,节 图,图,(Graph),是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、生物和计算机科学等领域中，图结构有着广泛的应用。奥林匹克信息学竞赛的许多试题，亦需要用图来描述数据元素间的联系。,图,G,由两个集合,V,和,E,组成，记为：,G=(V,，,E),，其中：,V,是顶点的有穷非空集合，,E,是,V,中顶点偶对,(,称为边,),的有穷集。通常，也将图,G,的顶点集和边集分别记为,V(G),和,E(G),。,E(G),可以是空集。若,E(G),为空，则图,G,只有顶点而没有边。,一、什么是

2、图？,很简单，点用边连起来就叫做图，严格意义上讲，图是一种数据结构，定义为：graph=（V，E）。V是一个非空有限集合，代表顶点（结点），E代表边的集合。,二、图的一些定义和概念,1.(a),有向图：图的边有方向，只能按箭头方向从一点到另一点。,(a)就是一个有向图。,2.(b),无向图：图的边没有方向，可以双向。,(b)就是一个无向图。,3.,结点的度：无向图中与结点相连的边的数目，称为结点的度。,4.,结点的入度：在有向图中，以这个结点为终点的有向边的数目。,5.,结点的出度：在有向图中，以这个结点为起点的有向边的数目。,6.,权值：边的“费用”，可以形象地理解为边的长度。,7.,连通：

3、如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V 是连通的,8.,回路：起点和终点相同的路径，称为回路，或“环”。,9.,完全图：一个n 阶的完全无向图含有n*(n-1)/2 条边；一个n 阶的完全有向图含有n*(n-1)条边；,稠密图：一个边数接近完全图的图。,稀疏图：一个边数远远少于完全图的图。,10.,强连通分量：有向图中任意两点都连通的最大子图。,下,图中1-2-5构成一个强连通分量。特殊地，单个点也算一个强连通分量，所以右图有三个强连通分量：1-2-5，4，3。,1,2,3,4,5,(a),1,2,3,4,5,(b),1,2,3,4,5,三、图的存储结构,1

4、.二维数组邻接矩阵存储,定义int G101101;,Gij的值，表示从点i到点j的边的权值，定义如下：,上图中的3个图对应的邻接矩阵分别如下：,0 1 1 1 0 1 1 5 8 3,G（A）=1 0 1 1 G（B）=0 0 1 5 2 6,1 1 0 0 0 1 0 G（C）=8 2 10 4,1 1 0 0 10 11,3 6 4 11 ,四、深度优先与广度优先遍历,从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组,visitedi,，未访问时值为,false,，访问一次后就改为,true,。,

5、图的遍历分为深度优先遍历和广度优先遍历两种方法，两者的时间效率都是,O(n*n),。,1.,深度优先遍历,深度优先遍历与深搜,DFS,相似，从一个点,A,出发，将这个点标为已访问,visitedi:=true;,，然后再访问所有与之相连，且未被访问过的点。当,A,的所有邻接点都被访问过后，再退回到,A,的上一个点（假设是,B,），再从,B,的另一个未被访问的邻接点出发，继续遍历。,例如对右边的这个无向图深度优先遍历，假定先从,1,出发,程序以如下顺序遍历：,125,，然后退回到,2,，退回到,1,。,从,1,开始再访问未被访问过的点,3,，,3,没有未访问的邻接点，退回,1,。,再从,1,开始

6、访问未被访问过的点,4,，再退回,1,。,起点,1,的所有邻接点都已访问，遍历结束。,1,2,3,4,5,2.,广度优先遍历,广度优先遍历并不常用，从编程复杂度的角度考虑，通常采用的是深度优先遍历。,广度优先遍历和广搜,BFS,相似，因此使用广度优先遍历一张图并不需要掌握什么新的知识，在原有的广度优先搜索的基础上，做一点小小的修改，就成了广度优先遍历算法。,五、一笔画问题,如果一个图存在一笔画，则一笔画的路径叫做欧拉路，如果最后又回到起点，那这个路径叫做欧拉回路。,我们定义奇点是指跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有以下两个定理。,定理,1,：存在欧拉路的条件：图是连通

7、的，有且只有,2,个奇点。,定理,2,：存在欧拉回路的条件：图是连通的，有,0,个奇点。,两个定理的正确性是显而易见的，既然每条边都要经过一次，那么对于欧拉路，除了起点和终点外，每个点如果进入了一次，显然一定要出去一次，显然是偶点。对于欧拉回路，每个点进入和出去次数一定都是相等的，显然没有奇点。,求欧拉路的算法很简单，使用深度优先遍历即可。,根据一笔画的两个定理，如果寻找欧拉回路，对任意一个点执行深度优先遍历；找欧拉路，则对一个奇点执行,DFS,，时间复杂度为,O(m+n),，,m,为边数，,n,是点数。,【,课堂练习,】,1,、【,NOIP2001,提高组,】无向图,G=(V,，,E),，其

8、中,V=a,b,c,d,e,f E=(a,b),(a,e),(a,c),(b,e),，,(c,f),(f,d),(e,d),，对该图进行深度优先遍历,得到的顶点序列正确的是（,）。,A,a,b,e,c,d,f,B,a,c,f,e,b,d,C,a,e,b,c,f,d,D,a,b,e,d,f,c,【,答案,】,D,【,分析,】依题中描述将无向图画出如图所示：,按照深度优先搜索的规则进行搜索，得到序列,a,b,e,d,f,c,。,2,、【,NOIP2002,提高组,】在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（,）倍。,A,1/2 B,1 C,2 D,4,【,答案,】,B,【,分析,

9、】在有向图中，所有顶点的入度之和等于所有顶点的出度之和。,3,、【,NOIP2003,提高组,】假设我们用,d=(a1,a2,.,a5),表示无向图,G,的,5,个顶点的度数，下面给出的哪（些）组,d,值合理（,）。,A,5,，,4,，,4,，,3,，,1 B,4,，,2,，,2,，,1,，,1 C,3,，,3,，,3,，,2,，,2,D,5,，,4,，,3,，,2,，,1 E,2,，,2,，,2,，,2,，,2,【,答案,】,BE,【,分析,】每条边被两个顶点计算度数，因此度数和必为偶数，,ACD,的度数和为奇数，因此正确答案为,BE,。,4,、【,NOIP2004,普及组,】在下图中，从顶

10、点（,）出发存在一条路径可以遍历图中的每条边一次，而且仅遍历一次。,A.A,点,B.B,点,C.C,点,D.D,点,E.E,点,【,答案,】,E,【,分析,】欧拉图问题，,E,是奇点。,5,、【,NOIP2005,普及组】,平面上有五个点,A(5,3),B(3,5),C(2,1),D(3,3),E(5,1),。以这五点作为完全图,G,的顶点，每两点之间的直线距离是图,G,中对应边的权值。以下哪条边不是图,G,的最小生成树中的边（,）。,A.AD B.BD C.CD D.DE E.EA,【,答案,】,D,【,分析,】笛卡尔坐标系画出来,生成树是,n-1,条总长最短的边连所有点。,6,、【,NOI

11、P2005,提高组,】平面上有五个点,A(5,3),，,B(3,5),，,C(2,1),，,D(3,3),，,E(5,1),。以这五点作为完全图,G,的顶点，每两点之间的直线距离是图,G,中对应边的权值。图,G,的最小生成树中的所有边的权值综合为（,）。,【,答案,】,D,【,分析,】根据,kruskal,算法,选取权值最小的、且不构成回路的边来产生最小生成树,因此,选出的边为,(A,D),(A,E),(B,D),(C,D),其权值和为,(2+2+2+sqrt(5),即答案为,D,。,7,、【,NOIP2007,提高组,】欧拉图,G,是指可以构成一个闭回路的图，且图,G,的每一条边恰好在这个闭

12、回路上出现一次（即一笔画成）。在以下各个描述中,不一定是欧拉图的是（,）。,A.,图,G,中没有度为奇数的顶点,B.,包括欧拉环游的图,(,欧拉环游是指通过图中每边恰好一次的闭路径,),C.,包括欧拉闭迹的图,(,欧拉迹是指通过途中每边恰好一次的路径,),D.,存在一条回路,通过每个顶点恰好一次,E.,本身为闭迹的图,【,答案,】,D,【,分析,】通过每个顶点一次的是哈密尔顿图，欧拉图是每条边一次，一笔画问题，闭迹回到起点封口。,8,、【,NOIP2004,普及组,】某大学计算机专业的必修课及其先修课程如下表所示：,课程代号,C,0,C,1,C,2,C,3,C,4,C,5,C,6,C,7,课程

13、名称,高等数学,程序设计语言,离散数学,数据结构,编译技术,操作系统,普通物理,计算机原理,先修课程,C,0,C,1,C,1,C,2,C,3,C,3,C,7,C,0,C,6,【,答案,】,D,【,分析,】拓扑排序：在学习,C5,之前要先学习,C3,和,C7,，,D,答案的,C5,排在了,C3,前面。,A.C,0,C,6,C,7,C,1,C,2,C,3,C,4,C,5,B.C,0,C,1,C,2,C,3,C,4,C,6,C,7,C,5,C.C,0,C,1,C,6,C,7,C,2,C,3,C,4,C,5,D.C,0,C,1,C,6,C,7,C,5,C,2,C,3,C,4,E.C,0,C,1,C,2,C,3,C,6,C,7,C,5,C,4,请你判断下列课程安排方案哪个是不合理的（,）。,谢谢,