图论基础ppt课件

图论基础,图论在信息学竞赛中占了很大部分,很多实际问题可以用图论来解决。,1,图的描述,2,图的表示,3,引例：试证：任意六个人在一起，其中一定有三个人彼此互相认识，或者有三个人彼此都不认识。,4,一、认识图型结构,图是图型结构的简称。它是一种复杂的非线性数据结构。图的二元组定义为：G=（V，E），其中V是非空的顶点集合，E是V上二元关系的集合。,5,1、图的分类：无向图、有向图、带权图,无向图：边集E（G）中为无向边。,有向图：边集E（G）中为有向边。,带权图：边上带有权的图。也称为网。（有向带权图、无向带权图）注意：不加权的图也可以认为所有边上的权都是1。,提问：指出上图中哪个是无向图、哪个是有向图、哪个是带权图？,6,练一练（1）：V(G1)=V1,V2,V3,V4,V5,V6;E(G1)=(V1,V2),(V1,V3),(V1,V4),(V1,V5),(V2,V5),(V3,V5),(V3,V6),(V4,V6),(V5,V6),练一练（2）：V(G2)=VA,VB,VC,VD,VE;E(G2)=,7,2、顶点的度、入度、出度,顶点的度：与该顶点相关联的边的数目，有奇点、偶点之分。,对于有向图：有入度和出度之分,入度：该顶点的入边的数目。出度：该顶点的出边的数目。,注意：顶点V的度等于它的入度和出度之和。,8,2,提问2：有向图中所有顶点的入度之和是(大于、等于、小于)所有顶点的出度之和；,提问3：任意一个无向图一定有（偶数、奇数）个奇点；,以上为关于图的度的三个定理,9,完全图：若是无向图中，则每两个顶点之间都存在着一条边；若是有向图，则每两个顶点之间都存在着方向相反的两条边。,3、完全图、稠密图、稀疏图,稠密图：当一个图的边数接近完全图时。,稀疏图：当一个图的边数远远少于完全图时。,n*(n-1)/2,n*(n-1),10,路径：对于图G=（V，E），对于顶点a、b，如果存在一些顶点序列x1=a,x2,xk=b(k1)，且（xi,xi+1）E，i=1,2k-1，则称顶点序列x1,x2,xk为顶点a到顶点b的一条路径，而路径上边的数目（即k-1）称为该路径的长度。并称顶点集合x1,x2,xk为一个连通集。,简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径；起点和终点相同的简单路径称为回路（或环）。,4、子图,图G,图G,设两个图G=（V，E）和G=(V,E),若V是V的子集,且E是E的子集,则称G是G的子图。,5、路径和回路,11,路径和简单路径的举例：,左图123是一条简单路径，长度为2，而13413就不是简单路径；右图121为一个回路。,12,连通图：如果一个无向图中，任意两个顶点之间都是连通的，则称该无向图为连通图。否则称为非连通图；左图为一个连通图。,连通分量：一个无向图的连通分支定义为该图的最大连通子图，左图的连通分量是它本身。,连通：在一个图中，如果从顶点U到顶点V有路径，则称U和V是连通的；,6、连通和连通分量,注意：任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。,13,强连通分量：一个有向图的强连通分量定义为该图的最大的强连通子图，右图含有两个强连通分量，一个是1和2构成的一个子图，一个是3独立构成的一个子图。,强连通图：在一个有向图中，对于任意两个顶点U和V，都存在着一条从U到V的有向路径，同时也存在着一条从V到U的有向路径，则称该有向图为强连通图；右图不是一个强连通图。,7、强连通图和强连通分量,注意：强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。,14,思考题,、某次聚会的成员到会时握了手，试证：与奇数个人握手的人数是一个偶数。,2、在一次象棋比赛中，任意两名选手间至多只下一盘，又每人至少下一盘,试证：总能找到两名选手，他们下过的盘数恰好相同；如果每名选手与其余所有的选手比赛过，且选手的人数为n，求比赛的总盘数。,3、在n个运动队间安排了一项竞赛，巳赛n+1局，试证：存在一个队，它至少参加过3局比赛。,15,二、图型结构的存储,图型结构的存储分为静态存储和动态存储。静态存储主要包括邻接矩阵、边集数组，动态存储主要有邻接表,1、邻接矩阵,邻接矩阵：是表示顶点之间相邻关系的矩阵。,设G(V，E)是具有n个顶点的图，顶点序号依次为1、2、n，则G的邻接矩阵是具有如下定义的n阶方阵。,16,有向图的邻接矩阵表示法,无向图的邻接矩阵表示法,17,有向带权图的邻接矩阵表示法,无向带权图的邻接矩阵表示法,18,图的邻接矩阵表示算法描述（以无向带权图为例）,Procedurecreate1(GA)；图用邻接矩阵存储Beginfori:=1tondoforj:=1tondoGAi,j:=maxint;Fork:=1toedo建立邻接矩阵Beginread(i,j,w);读入边（Vi，Vj)两端点序号及边上的权GAi,j:=w;GAj,i:=w;End；End；,19,2、邻接表,邻接表：是对图中的每个顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示方法。,注意：邻接矩阵用的是顺序存储的方式，而领接表是图的一种链式存储法。,对于无权图的边结点：,邻接点域,链域,对于有权图的边结点：,邻接点域,权域,链域,20,A图为无向图，它的邻接表为：,21,B图为有向图，它的邻接表为：,邻接表,逆邻接表,22,输入样式：421332,23,图的邻接表构造算法描述（以有向图为例）,Procedurecreate2(GL)；图用邻接表存储Beginfori:=1tondobeginread(GLi.data);GLi.link:=nil;end;fork:=1toedo建立邻接表Beginread(i,j);读入一条边的两端点序号new(s);s.adjvex:=j;s.next:=GLi.link;GLi.link:=s;End；End；,24,3、边集数组,边集数组：是利用一维数组存储图中所有边的一种图的表示方法。,起点,终点,权,无向带权图的边集数组表示法,25,图的边集数组表示算法描述（以无向带权图为例）,Procedurecreate3(GE)；图用边集数组存储Beginfork:=1toedoBeginread(i,j，w);读入一条边（Vi，Vj）的两端点序号及权值GEk.formvex:=i;GEk.endvex:=j;GEk.weight:=wEnd；End；,26,4、图的三种存储结构比较（n阶e条边）：,27,例1：建立带权无向图的邻接矩阵,Programcerategraph(input,output);constmax=1E5;n=10;typegraph=array1.n,1.nofreal;varI,j,k,e:integer;g:graph;w:real;Beginfori:=1tondoforj:=1tondogi,j:=max;read(e);fork:=1toedobeginread(i,j,w);gi,j:=w;gj,i:=w;end;,输入样式：525137412233248,28,fori:=1tondobeginforj:=1tondowrite(gi,j);writeln;end;end.,29,fork:=1toedobeginread(i,j);new(s);s.adjv:=j;s.next:=gi.link;gi.link:=s;end;end.,procedurecreatelist(varg:adj1);beginread(n,e);fori:=1tondobeginread(gi.v);gi.link:=nil;end;,例2：建立有向图的领接表,输入样式：71224323534654,30,1、图的深度优先遍历,对下面两个图分别进行深度优先遍历，写出遍历结果。注意：分别从a和V1出发。,左图从顶点a出发，进行深度优先遍历的结果为：a，b，c，d，e，g，f右图从V1出发进行深度优先遍历的结果为：V1，V2，V4，V8，V5，V3，V6，V7,图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。,三、图的遍历,31,对于一个连通图，深度优先遍历的递归过程如下：Proceduredfs(i:integer)；图用邻接矩阵存储Begin访问顶点i；Visitedi:=True；Forj:=1tondoIf(NotVisitedj)and(ai,j=1)Thendfs(j)；End；,以上dfs(i)的时间复杂度为O（n*n）。对于一个非连通图，调用一次dfs(i)，即按深度优先顺序依次访问了顶点i所在的（强）连通分支，所以只要在主程序中加上：fori:=1tondo深度优先搜索每一个未被访问过的顶点ifnotVisitedthendfs(i);,32,思考：如果图用邻接表存储，深度优先遍历的递归过程又如何？,Proceduredfs(i:integer)；图用邻接表存储Begin访问顶点i;visitedi:=true;p:=gi.link;whilepnildoBeginj:=p.adjvex;ifnotvisitedjthendfs(j);p:=p.next;End；End；,邻接表,33,对下面两个图分别从a和V1出发进行广度优先遍历，写出遍历结果。,2、图的广度优先遍历,左图从顶点a出发，进行广度优先遍历的结果为：a，b，d，e，f，c，g右图从V1出发进行广度优先遍历的结果为：V1，V2，V3，V4，V5，V6，V7，V8,34,深度优先遍历与广度优先遍历的比较：,深度优先遍历实际上是尽可能地走“顶点表”；而广度优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行广度优先遍历。,下面是广度优先遍历的过程：,35,时间：O（n*n）,Procedurebfs(i:integer)；广度优先遍历，图用邻接矩阵表示Begin访问顶点i；Visitedi:=true;顶点i入队q；while队列q非空dobeginhead:=head+1;v:=qhead；forj:=1tondobeginif(notVisitedj)and(av,j=1)thenbegin访问顶点j；Visitedj:=true;顶点j入队q;end;end;end;End；,36,四、欧拉图和哈密尔顿图,哥尼斯堡七桥问题,1、欧拉图,37,1）定义：,欧拉通路通过图中每条边一次且仅一次，并且过每一顶点的通路。,欧拉回路通过图中每条边一次且仅一次，并且过每一顶点的回路。,欧拉图存在欧拉回路的图。,2）定理1：存在欧拉路的条件：图是连通的，且存在0个或2个奇点。如果存在2个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。,定理2：存在欧拉回路的条件：图是连通的，且不存在奇点。,38,习题1、以下图形能否一笔画成？,练习：,习题2、“两只蚂蚁比赛问题”。两只蚂蚁甲、乙分别处在图G中的顶点a，b处，并设图中各边长度相等。甲提出同乙比赛：从它们所在顶点出发，走过图中所有边最后到达顶点c处。如果它们速度相同，问谁最先到达目的地？,39,3)寻找欧拉回路的算法,寻找欧拉回路的算法有多种，下面介绍一种基于递归的经典算法框架：find_circuit(结点i)；当结点i有邻居时选择任意一个邻居j；删除边(i,j)；find_circuit（结点j）；circuitcircuitpos:=结点i；circuitpos:=circuitpos+1；如果寻找欧拉回路，对任意一个点执行find_circuit；如果是寻找欧拉路径，对一个奇点执行find_circuit；算法的时间复杂度为O(m+n)。,40,周游世界游戏问题,2、哈密尔顿图,41,1）定义：,哈密尔顿通路通过图中每个顶点一次且仅一次的通路。,哈密尔顿回路通过图中每个顶点一次且仅一次的回路。,哈密尔顿图存在哈密尔顿回路的图。,2）判定：遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件。,42,判断下图是否具有哈密尔顿回路，通路。,练习：,43,3）寻找哈密尔顿环的算法到现在为止，寻找哈密尔顿环并没有一种有效的算法，一般只能用搜索解决。,44,图论试题的分析思路：1、建图（顶点集必须非空，关键是把什么抽象成顶点，什么抽象成边。）2、决定采用什么样的算法3、编写程序,五、应用举例,45,1、一笔画问题（one.?）问题描述编程对给定的一个图，判断能否一笔画出，若能请输出一笔画的先后顺序，否则输出“NoSolution！”。输入格式输入文件共n+1行，第1行为图的顶点数n，接下来的n行（每行n个数据）为图的邻接矩阵，Gi,j=1表示顶点i和顶点j有边相连，Gi,j=0表示顶点i和顶点j无边相连。输出格式若能一笔画出，则输出一笔画出的顶点先后顺序，否则输出“NoSolution！”。样例输入6010011101101010100011011100101110110样例输出5-1-2-3-4-2-6-4-5-6-1,46,programex1;constmaxn=100;varg:array1.maxn,1.maxnoflongint;du:array1.maxnoflongint;circuit:array1.maxnoflongint;n,circuitpos,i,j,start,oddnumber:longint;proceduresetIO;beginassign(input,one.in);reset(input);assign(output,one.out);rewrite(output);end;,procedurefind_circuit(i:longint);varj:longint;beginforj:=1tondoifgi,j=1thenbegingi,j:=0;gj,i:=0;find_circuit(j);end;circuitpos:=circuitpos+1;circuitcircuitpos:=i;end;,47,beginsetIO;read(n);fori:=1tondobegindui:=0;forj:=1tondobeginread(gi,j);dui:=dui+gi,j;end;end;,start:=1;oddnumber:=0;fori:=1tondoifduimod2=1thenbeginstart:=i;oddnumber:=oddnumber+1;end;if(oddnumber2)or(oddnumber=1)thenwriteln(NoSolution!)elsebegincircuitpos:=0;find_circuit(start);fori:=1tocircuitpos-1dowrite(circuiti,-);writeln(circuitcircuitpos);end;close(input);close(output);end.,48,2、铲雪（snow.?）随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。整个城市所有的道路都是双车道，因为城市预算的削减，整个城市只有1辆铲雪车。铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？输入：输入数据的第1行表示铲雪车的停放坐标（x,y），x，y为整数，单位为米。下面最多有100行，每行给出了一条街道的起点坐标和终点坐标，所有街道都是笔直的，且都是双向一个车道。铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转U型弯。铲雪车铲雪时前进速度为20km/h，不铲雪时前进速度为50km/h。保证：铲雪车从起点一定可以到达任何街道。输出：铲掉所有街道上的雪并且返回出发点的最短时间，精确到分种。输入样例：000010000100005000-100005000100005000100001000010000输出样例：3:55注解：3小时55分钟。,49,问题分析把一条路拆分成两条路，每一个点都是偶点了，所以这个图一定存在一条欧拉回路，这不正是题目所要求的吗？,参考程序,programex2;varppp,pp,h,m:longint;x1,y1,x2,y2,ans:real;beginassign(input,snow.in);assign(output,snow.out);reset(input);rewrite(output);readln(ppp);ppp为计算组数readln;forpp:=1topppdobeginifpp1thenwriteln;readln(x1,y1);ans:=0;whilenot(eoln)do,beginreadln(x1,y1,x2,y2);ans:=ans+sqrt(sqr(x1-x2)+sqr(y1-y2);距离公式累加end;readln;ans:=ans*2/1000/20;单位转化h:=trunc(ans);m:=round(60*(ans-h);ifm=60thenbeginm:=0;inc(h)end;write(h,:);ifm=1)and(ii=1)and(jjans2thenans2:=roomi;writeln(ans2);,57,ans3:=0;fori:=1tondoforj:=1tomdofort:=3to4dobeginii:=i+wayt,1;jj:=j+wayt,2;if(ii=1)and(ii=1)and(jjmarkeri