《图论基础课件》由会员分享，可在线阅读，更多相关《图论基础课件（46页珍藏版）》请在金锄头文库上搜索。
1、图 论,图论的基本概念,图论是一新的数学分支，也是一门很有实用价值的学科，它在自然科学、社会科学等各领域均有很多应用。近年来它受计算机科学蓬勃发展的刺激，发展极其迅速。应用范围不断拓广，已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学以及数学的其它分支中。特别在计算机科学中。如形式语言、数据结构、分布式系统、操作系统等方面均扮演着重要的角色。,我们经常看到，导游图、铁路和公路的路线图、程序流程图等都是用图形表示的。这些图形都以某种形式简捷地表现其对象的本质和关键，从而让人们通过观察，能很好地了解该图所表示的事物。,Konisberg七桥问题(或Euler回路问题),游人从两岸A，
2、B或两个小岛C，D中任一个地方出发，要找到一条路线做到每座桥恰通过一次而最后返回原地。,A,B,C,D,1736年，当时著名的数学家Euler仔细研究了这个问题，他将上述四块陆地与七座桥间的关系用一个抽象图形来描述，其中A，B，C，D分别用四个点来表示，而陆地之间有桥相连者则用连接两个点的连线来表示，这样上述的七桥问题就变成为由点和边所组成的图论问题。 试求从图中的任一点出发，通过每条边一次，最后返回到该点，这样的路径是否存在?,关于七桥问题的回答是否定的。直观上不难发现，为了要回到原来的地方。要求与每一个顶点相关联的边的数目，均应为偶数，从而可得从一条边进入，而从另一条边出去，一进一出才行。
3、在此基础上。Euler找到了一般的图存在这样一条回路的充分必要条件。,定义 对于连通的无向图G，若存在一简单回路，它通过G的所有边，则这回路称为G的(Euler)回路。 定理 若连通无向图G的所有顶点的度都是偶数，则存在一条图G的Euler回路。,什么是图？ 有序对G(V(G)，E(G)称为一个图，其中V(G)是一个非空有限集。V(G)中的元素称为G的顶点，E(G)是V(G)中全体不同元素构成的不同无序对整合的一个子集，E(G)中的元素称作G的边。我们称V(G)是图G的顶点集，E(G)为G的边集；在不致混淆的情况下，有时分别用V和E表示G的顶点集和边集。G的顶点数|V(G)|有时也称作G的阶，
4、通常用p来表示；G的边的数目|E(G)|一般用q表示。为方便，我们通常用uv来表示边u,v(其中u，v是V(G)的元素)。如果euv E(G)，则说e关联u和v，称u,v分别是e的端点，并且称这两个顶点是相邻的。,在图的定义中，如果删去“边必须是不同的”的限制，则导致的结果称为多重图。,连接同一对顶点的两条或者更多条边(但必须有限)被称为多重边或平行边。,如果再在多重图中则去“边必须连接不同顶点”的限制，即允许有自环的存在，则由此导出的结果称为一般图。,A,B,C,D,有向图和无向图,在图(或简单图)的定义中，如果我们把“无序”二字改成“有序”二字，便得到所谓有向图的概念。更确切地讲，所谓有向
5、图D是一个有序对(V(D)，A(D)，其中V(D)是一个非空有限集，V(D)中的元素称为顶点，A(D)是由V(D)中的元素组成的一些有序对构成，并且要求：构成有序对的两个元素不同，任何两个有序对不同。显然A(D)是一个有限集。A(D)中的元素称为弧。,A,B,C,D,赋权图G是一个三元组（V，E，g），其中V是顶点集，E是边集，f是定义在V上的函数，g是定义在E上的函数，f(vi)和g(ej)分别称为顶点vi和边ej上的权。,赋权图,A,B,C,D,5,3,3,7,如果图G是一个简单图，并且每两个顶点之间都有一条边，我们就称G为完全图通常将具有n个顶点的完全图记为Kn,完全图,如果图G的两个顶
6、点vi与vj之间有边相连，就说点vi与vj是相邻的，否则就说点vi与vj是不相邻的如果顶点v是边e的一个端点，就说点v与边e是相邻的，e是从v引出的边从一个顶点v引出的边的条数称为v的次数，记作degGv，在不致混淆的时候，也可以写成degv,第1题： 完全图Kn有多少条边？,习题讲解,第2题：有n个药箱，每两个药箱里有一种相同的药，每种药恰好在两个药箱里出现，问有多少种药？,习题讲解,药箱,药,第3题： 下述叙述中正确的是： 竞赛图是一般图 含有自环的图不是一般图 如果两个顶点间有两条边，它们是平行边 完全图中必有一个顶点次数大于等于3 一般图包含任何图,习题讲解,第4题： 下述对赋权图的正
7、确描述是： 赋权图指的是图的边带权值 赋权图指的是图的顶点带权值 图的存储一般来说用邻接矩阵，赋权图则不能 没有权值的图可以看作权值都为1的赋权图,习题讲解,第5题： 下面两个图同构吗？,习题讲解,v1,v2,v3,v4,v5,v6,v7,v1,v3,v5,v7,v2,v4,v6,第6题： 旅行者能否经过每一座桥恰好一次，既无遗漏也无重复？,习题讲解,相应的图有两个奇顶点（D，E），因而可以一笔画成,第7题： 四个村庄下面各有一个防空洞甲、乙、丙、丁，相邻的两个防空洞之间有地道相通，并且每个防空洞各有一条地道与地面相通，能否每条地道都恰好走过一次，既无重复也无遗漏?,习题讲解,相应的图有四个奇
8、顶点（甲，乙，丙，丁），因而不可以一笔画成,第8题： 在图中是否能找一条链经过每个顶点恰好一次(并不要求经过所有边)?,习题讲解,将顶点涂上黑色或白色，使得相邻顶点颜色互不相同如果所说的链存在那么在链上的顶点必然黑白相间，因此黑的顶点与白的顶点的个数相同或相差1，但图中黑点个数为7，白点个数为9，相差为2，因此所说的链不可能存在。,第9题： 12只杯子，杯口全部朝上，如何将它们全部翻过来，使得杯口全部朝下？但规定每一次翻动时，必须11只杯子一起翻动 需翻动11次 需翻动12次 需翻动13次 不能实现,习题讲解,翻动12次，使12种可能的组合各出现一次，从而每只杯子恰好翻动11次，变为杯口朝下,
9、第10题： 13只杯子，杯口全部朝上，如何将它们全部翻过来，使得杯口全部朝下？但规定每一次翻动时，必须12只杯子一起翻动 需翻动12次 需翻动13次 需翻动15次 不能实现,习题讲解,不可能，因为若干次翻动的杯子的总个数为偶数。而如果可能翻成杯口朝下的话，每只杯子均翻动奇数次，因而13只杯子翻动的总次数也是奇数。,图,图是由一些点和这些点之间的连线组成的。 1.结点和边:我们把图中的点称为结点,把两结点之间的连线称作边. 2.相邻:若两个结点之间由一条边连接,则称这两个结点是相邻的. 3.无向图和有向图:如果不考虑边的方向,这样的图叫作无向图;反之,若边是有方向的,则这样的图称为有向图,有向图
10、要用箭头标明边的方向.(树是一种有向图的特例.),4.带权图:如果一个图在标明两个结点的从属关系的同时,又标明了两者的数量关系(如两地的距离),这样的图叫带权图. 5.结点的度数:与一个结点相关联的边的个数称为该结点的度数. 6.路:如果从一个结点出发,沿着某些连续地移动而到达另一个指定的结点,这种依次由结点和边组成的序列,就形成了一条路.,图的表示方法和基本操作,在程序中,我们可以用一个二维数组来表示一个图及其各结点的 邻接关系(邻接矩阵).此二维数组(矩阵)各元素定义为:,对于带权图,邻接矩阵则要表示出各边的长度:,显然,无向图的邻接矩阵是对称的,即若Vi Vj有边,则Vj Vi 必有边.
11、,例,例,例：A，B，C，D，E，F这六个城市，它们之间的交通 情况如图所示，其中箭头方向表示有单向通路。现在要 求从键盘输入一个出发点和一个到达点，判断有无通路， 并打印通路所经各点。,数组A：,0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0,数组B：用来存放找到的这条通路的各个点。,方法：从输入的起点开始试探，每一步都有5种方案， 如果对应数组AI，J1，表示有路可走，否则试下 一个结点，若走到死胡同（所有结点都试过了均无路 可走），则回溯上一步，换一个方案继续试走。,主程序：,给数组a赋初值,
12、并把数组b初始化,输入起点s,终点e,累加路径条数的计数器z 0,表示当前是第几步的step 1; bstep s,调用递归过程try(s),Z=0,y,n,输出无通路,K0,k k+1,(AI,k=1)and(ks),y,n,step step+1; bstep k,k=e,y,n,z z+1,Try(k),打印这条通路,bstep 0; step step-1,Until k=n,过程：try(i),欧拉(Euler)回路 定义 对于连通的无向图G，若存在一简单回路，它通过G的所有边，则这回路称为G的(Euler)回路。 定理 若连通无向图G的所有顶点的度都是偶数，则存在一条图G的Eule
13、r回路。 推论 如果连通图G只有两个度为奇数的顶点，则存在一条以这两顶点为两端点，包含G的所有边的简单道路。这道路称之为Euler道路。,编程找出如图的一笔画路线,5,1,6,4,3,2,构造邻接矩阵,0 1 0 0 1 1 1 0 1 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 0,数组links,计算每个点的度数存dgrI中,总度数存sum中,奇点个数存odt中，若有奇点，则最后一个奇点位置存start中。,sum:=0;odt:=0;start:=1,dgri:=0;,For i:=1 to n do,For j:=1 to n
14、 do,dgri:=dgri+linksI,j,sum:=sum+dgri,If odd(dgri) then odr:=odt+1;start:=i,Until sum=0,r:=0,r:=r+1,linksnowd,r0 and dgrr1,OR dgrr=1 and sum=2,linksnowd,r:=0;linksr,nowd:=0,dec(dgrnowd);dec(dgrr),sum:=sum-2;write(,r),nowd:=r,program as; const n=6; links:array1n,1n of integer= (0,1,0,0,1,1),(1,0,1,1,
15、0,1),(0,1,0,1,0,0), (0,1,1,0,1,1),(1,0,0,1,0,1),(1,1,0,1,1,0); var dgr:array1n of integer; i,j,r,sum,odt,start,nowd:integer;,procedure find; begin sum:=0;odt:=0;start:=0; for i:=1 to n do begin dgri:=0; for j:=1 to n do dgri:=dgri+linksi,j; sum:=sum+dgri; if odd(dgri) then begin odt:=odt+1;start:=i end; end; end;,BEGIN find; if odt2 then begin writeln(no sulution.);exit end; nowd:=start; write(start); repeat r:=0; repeat r:=r+1; until (linksnowd,r0) and (dgrr1)or(dgrr=1) and (sum=2); linksnowd,r:=0;linksr,nowd:=0;sum:=sum-2; d
