《图论的介绍ppt课件.ppt》由会员分享，可在线阅读，更多相关《图论的介绍ppt课件.ppt（108页珍藏版）》请在三一办公上搜索。
1、图论的介绍,哥尼斯堡七桥问題(Bridges of Koenigsberg),能不能走过每一个桥刚好一次并且回到原來的地方？,欧拉路径解決哥尼斯保七桥问題,原來是一笔画问题啊！,数学家欧拉(Euler,1707-1783)于1736年严格的证明了上述哥尼斯堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式,实际生活中的图论Graph Model,电路模拟,例：Pspice、Cadence、ADS.,Pspice,Cadence,交通网络,航空网络!,捷運路線图！,网络架构图,计算机网络,有向图,有单行道的街道！,行程表！,Social Network,High School Datin
2、g,corporate e-mail,Reference:Bearman,Moody and Stovel,2004image by Mark Newman,Reference:Adamic and Adar,2004,Protein interaction network,Reference:Jeong et al,Nature Review|Genetics,Power transmission grid of Western US,The Internet,The Internet as mapped by The Opte Projecthttp:/www.opte.org,More
3、Applications,Hypertexts网页包含到其他网页的超链接。整个Web是一个图.搜索引擎需要图处理算法。Matching职位招聘，如何有效将职位与应聘者匹配？Schedules工程项目的任务安排，如何满足限制条件，并在最短时间内完成？Program structure大型软件系统，函数（模块）之间调用关系。编译器分析调用关系图确定如何最好分配资源才能使程序更有效率。,Graph Applications,Graph Problems and Algorithms,哈密頓（Hamilton）周遊世界问題,哈密頓路径至今尚无有效方法來解決！,正十二面体有二十个顶点表示世界上20个城市
4、各经每个城市一次最后返回原地,投影至平面,最短路径问題(Shortest Path Problem),最快航線,最快的routing,最短路径算法Dijkstra算法,可以求出從某一点到图上其他任一点的最短路径,走迷宫与深度优先搜索(Depth-First Search),老鼠走迷宮深度优先搜索,一直往前走碰壁就回头換条路找沿途要记录下走过的路线,Some graph-processing problems,Path.Is there a path between s to t?Shortest path.What is the shortest path between s and t?Lo
5、ngest path.What is the longest simple path between s and t?Cycle.Is there a cycle in the graph?Euler tour.Is there a cycle that uses each edge exactly once?Hamilton tour.Is there a cycle that uses each vertex exactly once?Connectivity.Is there a way to connect all of the vertices?MST.What is the bes
6、t way to connect all of the vertices?Biconnectivity.Is there a vertex whose removal disconnects the graph?Planarity.Can you draw the graph in the plane with no crossing edges?First challenge:Which of these problems is easy?difficult?intractable?,图论的术语,什么是图？,一堆顶点和边的组合！Set of vertices connected pairwi
7、se by edges.,例一 例二,图论的术语,顶点(Vertex)边(Edge)一个图G=(V,E)V:顶点的集合E:边的集合例：如右图V=a,b,c,d,eE=(a,b),(a,c),(a,d),(b,e),(c,d),(c,e),(d,e),再來一些术语,连通图(connected graph)子图(subgraph)树(tree)沒有回路的连通图森林(forest)一堆树的集合,树的实例 行政组织图,有向图(Digraph),有向图(Digraph),有向且无简单回路的图(directed acyclic graph),加权图(Weighted Graph),生成树(Spanning
8、 Tree),生成树,包括图中所有的顶点，并且是一棵树,可运用生成树的实例,Graph Terminology,一些特殊的图,完全图 Complete graphs,任意两点之间都有一条边与其相连的图称为完全图，以Kn 來表示，n为顶点数,二分图（偶图）Bipartite graphs,A graph that can be decomposed into two partite sets but not fewer is bipartiteIt is a complete bipartite if its vertices can be divided into two non-empty
9、groups,A and B.Each vertex in A is connected to B,and vice-versa,Complete bipartite graph K2,3,The graph is bipartite,平面图 Planar graphs,A planar graph is a graph that can be embedded in a plane so that no edges intersect,Planar:,=,NOT Planar:,平面图实例,8个顶点(V=8)12条边(E=12)6个面(F=6)8-12+6=2,更多平面图实例,树 Trees
10、,树(tree):连通无简单回路无向图若有n个顶点，則有n-1条边任两点之间仅有一条路径生成树(spanning tree):包括图中所有的顶点，并且是一棵树,A connected graph G,Spanning trees of G,tree,图术语回顾,点：研究对象（陆地、路口、国家、球队）；,点间连线：对象之间的特定关系（陆地间有桥、路口 之间道路、两国边界、两球队比赛及结果)。,对称关系：桥、道路、边界；,用不带箭头的连线表示，称为边。,非对称关系：甲队胜乙队，用带箭头的连线表示，称为弧。,图：点及边（或弧）组成。,例：有甲、乙、丙、丁、戊五个球队，各队之间比赛 情况如表：,点：球
11、队；连线：两个球队之间比赛过，如甲胜乙，用 v1 v2表示。,图的定义,定义1：一个图，是由非空集合V(G)=vi 和V(G)中 元素的有序对（或无序对）的集合E(G)=ek 所组成的二元组（V(G)，E(G)）所构成。记为 G=（V(G)，E(G)）,简记 G=（V，E）,其中 V=vi 称为点集，vi为点。E=ek称为边集，ek为边（或弧）。,当V，E为有限集时，称G为有限图。否则，称G为无限图。,无向图：由点及边构成，边vi，vj,有向图：由点及弧构成，弧（vi，vj）,图G中点集V的顶点个数，记为p(G)；边数记为q(G),简记 p，q。,1.简单图与多重图,某条边两个端点相同，称这条
12、边为环。若两点之间有多于一条的边，称这些边为多重边。,无环、无多重边的图称为简单图。,多重图：无环、但允许有多重边。,二、图论中常用术语,2.相邻与关联,若边e=u，vE，称u，v是e的端点，也称u，v是相邻的。称e是点u（及点v）的关联边。,若两条边有一个公共的端点，则称这两条边相邻接。,点与边关联,点与点相邻,边与边相邻接,定理1 图G=（V，E）中，所有点的次之和为边数的两倍，即,3.奇点与偶点,次为奇数的点称为奇点，否则称为偶点。,定理2 任一图中奇点的个数为偶数。,证明：设v0和v e分别是G中的奇点和偶点的集合，由定理1，有,因 是偶数，也是偶数，故必为偶数。即在一个图中奇点的个数
13、必为偶数。,4.节点度与悬挂点、孤立点,图G中以点v为端点的边的数目，称为v在G中的度，记为d（v）。,d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1,度为1 的点为悬挂点，悬挂点的关联边称为悬挂边，度为零的点称为孤立点。,5.链与圈,给定一个图G=（V，E），G中的一个点、边交错序列（vi1，ei1，vi2，ei2，vik-1，eik-1，vik），如果满足eit=vit，vit+1（t=1，2，k-1），则称为一条联接vi1和vik的链，记为=（vi1，vi2，vik）。,链（vi1，vi2，vik）中，若vi1=vik，称之为一个圈，记为C=（vi1，vi2，vik-1，
14、vi1）。,初等链：链中点都不同。简单链：链中边都不同。,（边能否相同？）,（点能否相同？）,简单链：1=（v2，v1，v3，v6，v4，v3，v5）,初等链：2=（v2，v1，v3，v5）,简单圈：C1=（v1，v2，v4，v3，v5，v6，v3，v1）,初等圈：C2=（v1，v2，v4，v6，v5，v3，v1）,有向图中，不考虑弧的方向，有类似链（圈）的定义。当链（圈）上弧的方向一致时，称为路（回路）。,3.连通图,给定图G=（V，E），任何两点间至少有一条链，则称G是连通图，否则为不连通图。,若G是不连通的，它的每个连通部分称为G的连通分图。,一些特殊图类,1.平凡图 节点数n=1,边数
15、m=0的图。,2.零图 边数m=0的图。,5.完备图,无向图的完备图：任何两点之间有一条边；,有向图的完备图：任何两点u与v之间有两条有向边（u，v）及（v，u）。,基本图：把有向图的每条边除去方向得到的无向图。,若V(G)=X Y,X Y=，X、Y中的任两顶点不相邻，则G称为二分图，记为（S,X,Y）。,4.树 无圈连通图。,6.二分图,9.网络,若对图G=（V，E）中每条边vi，vj赋予一个数wij，则称wij为边vi，vj的权，并称图G为网络（或赋权图）。,网络：无向网络、有向网络。,7.完全二分图 若V(G)=(S,X,Y),如果任意X、Y，都有，E，则称G是完全的二分图。,8.正则图
16、 如果G中每个点的次数都相同，则G叫做正则图。,1.子图与支撑子图,定义2 给定图G=（V，E），若图G1=（V1，E1），其 中V1V，E1=uv|uvE，u，v v1，则称G1是G的子图。,定义3 给定图G=（V，E），若图G1=（V，E1），其 中E1E，则称G1是G的一个支撑子图。,点全部保留,支撑子图,四、图的运算,2.图的收缩运算,设图G=(V,E)，V1 V,在G中收缩V1是指在图G中，在V1中的点重为一个点，G与V1中的点相关联的边变为与这个新点相关联的边，称这样的图为关于V1收缩。,3.割集,给定图G=（V，E），点的子集S V，T V，定义G中边的集合S，TG=uv|u s
17、，v T为一个割集。,若X=v1,若X=v1，v2，,4.图的同构,定义4 设图G=（V，E）与G1=（V1，E1），若它们的点之间存在一一对应，并且保持同样的相邻关系，则称G与G1同构。记为GG1。,(a),(b),图(a)和(b)就为同构,五、图的矩阵表示,图的矩阵表示方法有：邻接矩阵、关联矩阵、可达矩阵、权矩阵等。,1.邻接矩阵,邻接矩阵用于描述两个顶点之间是否有边（弧）相连。,对于有n个顶点的无向图G=(V,E)，定义邻接矩阵(B=bij)nn。其中，,对于有几个顶点的有向图G=(V,A)，定义邻接矩阵(B=bij)nn。其中，,例题1 已知无向图所示，求其邻接矩阵。,则,显然，无向图
18、的邻接矩阵是关于对角线的对称矩阵。,例 2 已知：图所示，求其邻接矩阵。,则：,v1 v2 v3 v4 v5 v6 v1 0 1 1 0 0 0 v2 0 0 1 1 1 0 v3 0 0 0 1 0 0 v4 0 0 0 0 1 1 v5 0 0 1 0 0 1 v6 0 0 0 0 0 0,其邻接矩阵为：,当G为无向图时，邻接矩阵为对称矩阵。,在有向图中可达矩阵用于描述两点之间是否有路相连,即R=(rij)nn,其中，,2.可达矩阵,例题3 求例题2的可达矩阵,则,v1 v2 v3 v4 v5 v6 v1 1 1 1 1 1 1 v2 0 1 1 1 1 1 v3 0 0 1 1 1 1
19、v4 0 0 0 1 1 1 v5 0 0 0 0 1 1 v6 0 0 0 0 0 1,3.关联矩阵,有向图的关联矩阵也称顶点边关联矩阵。,设有向图 G=(V,A)，其中rij=V=v1,v2,v3vn，则关联矩阵可定义为 M=(mij)nm其中：,例题4 求下图的关联矩阵,则其关联矩阵为：,a1 a2 a3 a4 a5 a6 v1 0 1-1 0 0-1 v2 1 0 1 1 0 0 v3-1-1 0 0 1 0 v4 0 0 0-1-1 1,权矩阵是最流行的一种网络矩阵表示法。对于有n个顶点的无向网络G=(V,E,W),边 vi,vj的权为wij，则权矩阵D=(dij)nn，其中：,4.
20、权矩阵,对于有n个顶点的有向网络G=(V,A,W),边 vi,vj的权为wij，则权矩阵D=(dij)nn，其中：,例题5.如图所示，弧上的数字代表数，D=(dij)5 5。,0 35 4319 0 85 18 43 0 11 0 16 77 0,其权矩阵为：,基 本 概 念,最 短 路 问 题 及 其 算 法,固 定 起 点 的 最 短 路,最短路是一条路径，且最短路的任一段也是最短路,假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树,因此,可采用树生长的过程来求指定顶点到其余顶点的最短路,算法步骤：,u1,u2,u3,u4,u5,u6,u7,u8,一、
21、可化为最短路问题的多阶段决策问题,二、选 址 问 题,1、中心问题,2、重心问题,可化为最短路问题的多阶段决策问题,选址问题-中心问题,S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5,S(v3)=6,故应将消防站设在v3处。,选址问题-重心问题,还有哪些选址问题？,消防队汽车急救中心警车配置和巡逻问题（2009研究生数学建模竞赛试题）,警车配置和巡逻问题,110警车在街道上巡弋，既能够对违法犯罪分子起到震慑作用，降低犯罪率，又能够增加市民的安全感，同时也加快了接处警（接受报警并赶往现场处理事件）时间，提高了反应时效，为社
22、会和谐提供了有力的保障。该问题考虑到某城市内一区域，并假定所有事发现场均在下图的道路上。下图红点部位为重点部位，该区域内三个重点部位的坐标分别为：（5112，4806），（9126，4266），（7434，1332），蓝色部分为水域，相邻两个交叉路口之间的道路近似认为是直线。,警车配置和巡逻问题,警车配置和巡逻问题,现在该城市拟增加一批配备有GPS卫星定位系统及先进通讯设备的110警车。假设110警车的平均巡逻速度为20km/h，接警后的平均行驶速度为40km/h。警车配置及巡逻方案则需要尽量满足以下要求：D1.警车在接警后三分钟内赶到现场的比例不低于90；而赶到重点部位的时间必须在两分钟之内
23、。D2.使巡逻效果更显著。D3.警车巡逻规律应有一定的隐蔽性。,警车配置和巡逻问题,具体问题如下：一.若要求满足D1,该区最少需要配置多少辆警车巡逻？二.请给出评价巡逻效果显著程度的有关指标。三.请给出满足D1且尽量满足D2条件的警车巡逻方案及其评价指标值。四.在第三问的基础上，再考虑D3条件，给出你们的警车巡逻方案及其评价指标值。五.如果该区域仅配置10辆警车，应如何制定巡逻方案，使D1、D2尽量得到满足？六.若警车接警后的平均行驶速度提高到50km/h，回答问题三。七.你们认为还有哪些因素、哪些情况需要考虑？给出你们相应的解决方案。,警车配置和巡逻问题,新问题,单约束选路问题？多约束选路问
24、题？多目标选路问题？多路径选路问题？区间最优路径？,匹配与最大匹配,定义:(二部)图 G=X,E,Y 的边集E的子集M称为G的一个匹配,如果M的任二边都没有公共端点;G中边数最多的匹配称为最大匹配(不唯一);含有G的每一点的匹配称为完美匹配(必为最大匹配仍不唯一).下面是最大,完美匹配的例子(用粗线表示):,工作分配问题,问题 某教研室有4位教师:A,B,C,D.A能教课程5;B能教1,2;C能教1,4;D能教课程3.能否适当分配他们的任务,使4位教师担任4门不同课并且不发生安排教师教他不能教的课的情况?此问题可归结为二部图的数学模型:G=A,B,C,D,E,1,2,3,4,5,(X,y)E,
25、如果X能教y.一个满足要求的工作分配正是一个含有4条边的一个最大匹配.,A,B,C,D,1,2,3,4,5,求图G最大匹配的方法,首先 任取一个匹配(含一边也可)M作为起点.接着按下列方法逐步调整当前匹配(每一步使它调整为边数多1的匹配)最后达到一个最大匹配:步骤 在X中选定一个不属于M的点xi标记(*).步骤 在X的新标记的点中选一点,如xi,用(xi)标记通过不属于M的边与xi邻接并且尚未标记的点(如yi);在Y的新标记的点中选一点(如yi),用(yi)标记通过M的边与yi邻接并且尚未标记的点;照此继续,直到发现标记到Y的一个点,该点不与X中任一边相关联或标记不到任何这样的点为止.出现前一
26、情况,便找到一条关于M的交替链(定义8.4-4);利用它可调整M到一个比M多一边的匹配;出现后一情况便表示M已为最大匹配.,求最大匹配举例,解:取一个初始匹配M=Bb,Cc,Dd.用标记法从点A开始求得一条交替链:=(AcCe)(左图).用调整匹配M:将中属于M的边删去并将其中不属于M的其它边添加到M中得到比M多一边的新匹配M(如右图示).因对M用标记法只能从E或F开始,但都不能求出M的任何交替链,故判定M是一个最大匹配.,A(c),B,C,D(d),a,b,c(D),d(E),e,E(*),F(*),f,A(*),B,C(c),D,a,b,c(A),d,e(C),E,F,f,M,树的概念,树
27、是应用中特别重要的特殊图,分无向树和有向树两种.定义 无回路的无向连通图称为无向树.也可以说,无基本回路的无向连通图称为无向树,因为:无回路等价于无基本回路.连通分支全为无向树的图,即无回路的无向图,称为森林.树的1度点称为树叶,不是树叶的点称为分枝点.例 图8.6-1.,(n,m)无向线图G是树的5个等价条件,G是树连通无回路.G无回路且m=n-1.G连通且m=n-1.G无回路且加一边得唯一回路.G连通且少一边不连通.G任二点间有唯一(基本)路径.证:2结点树的边数为1=2-1.假设k结点树的边数为k-1.要证k+1结点树的边数为k.事实上,树G必有一树叶w(否则G任一点的度都大于1,从任一
28、点出发沿一边进入另一点恒可沿另一边离开.因G的结点有限,故有限步以后一定要回到前面的点,便与G无回路相矛盾).子图G-w显然是树,其点数是k,按归纳假设其边数是k-1,从而G的边数是k=(k+1)-1,归纳证明完成.,证:要证若G无回路且m=n-1,则G连通.不然的话,G有k(2)个无回路的连通分支(树):T1,Tk,设Ti为(ni,mi)图,则 m=m1+mk=(n1-1)+(nk-1)=(n1+nk)-kn-1矛盾.:要证若G连通且m=n-1,则G无回路且加一边得唯一回路.先对n用归纳法证明G无回路.n=2时显然成立.设n=k时结论已成立并考虑n=k+1的情形.此时若G无1度点,则2m2n
29、 与m=n-1矛盾.故G必有1度点w.易见G-w连通且满足条件(边数比点数少1),由归纳假设G-w无回路.因w为1度点,故G也无回路.再证G加任一边e=(vi,vj)得唯一回路.G连通性保证有vi-vj路,从而G+e有回路.因删去两条回路中的任一边仍有回路留下,故G+e不会有两条回路(否则G有回路).,证:要证若G无回路且加一边得唯一回路,则G连通且删去一边不连通.用反证法,因G是森林,若G不连通,则在G的二连通分支的点间加边不会得新回路,故G连通.若连通的G删去一边e还连通,便得出G=(G-e)e有回路的矛盾.:要证若G连通且删去一边不连通,则G任二点间有唯一路径.事实上,G连通性保证任2点
30、u,w间有路径.若有两条这样的u-w路径便与G删去一边不连通的假设矛盾.:要证若G任二点间有唯一路径则G是树.任2点都可达表示G连通.若G有回路,则G必有两点其间有两条路径,与条件矛盾.,推论,由条件,树是结点数固定下边数最少的连通图,并且minm|(n,m)图连通=n-1.由条件,树是结点数固定下边数最多的无回路图,并且maxm|(n,m)图无回路=n-1.每棵树至少有两片树叶(n2).证:若不是这样便有d(v1)+d(vn)2(n-1)+12(n-1)=2m,与d(v1)+d(vn)=2m的已知规律矛盾.,生成树的概念,定义 无向图G=V,E的生成子图T是树,则称T是G的一棵生成树(不唯一
31、,图8.6-2).任何连通无向图G至少有一棵生成树.证(破圈法)若G无简单回路,则G自己是一棵生成树.否则,G有简单回路C1,删去C1的一边所得G的生成子图记为G1.若G1无回路,则G1为生成树;否则G1有简单回路C2,删去C2的一边所得G1的生成子图记为G2.若G2无回路,则G2为生成树;否则,照此继续.易见经m+1-n步必可找到G的一棵生成树.推论 无向图G连通当且仅当G有生成树.,最小生成树的概念,定义 赋权简单连通无向图G=V,E,W的子图 H的权定义为 H 的所有边的权和.G中权最小的生成树称为最小生成树(对普通简单连通图不考虑最小生成树).最小生成树有很强的应用背景,例如:设计联系
32、若干城市的最短线路通信网;设计供应若干居民点的最短自来水管线路等.,求最小生成树的Kruskal算法(避圈法),算法 将赋权简单连通无向图G的边排序:e1e2em.开始时 k:=1,A:=.步骤 若Aek导出的子图无回路,则 A:=Aek.步骤 若|A|=n-1,算法结束;否则转步骤.例 对左边无向图用Kruskal算法求得右边的最小生成树.1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7=n-1,1,2,3,4,5,6,7,8,9,10,11,12,1,2,3,5,6,8,9,Kruskal算法的正确性,证明:由Kruskal算法必可求得赋权简单图G的一棵生成
33、树T0(因G连通),不妨令T0的边为e1,en-1.若T0不是最小生成树,则G的每棵最小生成树对应一个i,使得ei+1T但e1,eiT(i=0表示T与T0无公共边).由于最小生成树有限,我们取T为对应最大i的那棵最小生成树.于是,T+ei+1有唯一基本回路C(包含ei+1).因树T0无回路,故有边fC且fT0,即fT-T0.在T中以ei+1代f(仍无回路)得新生成树T=T+ei+1-f,其权为W(T)=W(T)+W(ei+1)-W(f)W(T).于是W(ei+1)W(f).因T为树,e1,ei,f诱导的子图无回路,从而由Kruskal算法选边的过程知W(ei+1)W(f).所以W(ei+1)=
34、W(f).这意味着W(T)=W(T),即T也是G的最小生成树.但T包含e1,ei,ei+1,他比T对应更大的i值,引出矛盾.得证必须是最小生成树.,求最小生成树的破圈法,此法1975年由中国数学家管梅谷教授首先提出,具体算法如下:将赋权简单连通无向图G=V,E的边排序:e1e2em.开始时 A:=E.步骤 若A无回路,则A是最小生成树,算法结束,否则转步骤.步骤 在A中任取的一条回路C中取有最大权的边e,置A:=A-e后转步骤.破圈法的正确性基于下列事实(定理8.6-9):G的任何一条简单回路C中权最大的边f一定不属于任何最小生成树T.(C必有一边e不属于T,若f属于T,则以e代f所得的生成树
35、T的权W(T)=W(T)+W(e)-W(f)W(T),产生矛盾.),树叶,分枝点,子树的概念,有根树的典型例子是家谱树.树根是家谱的第一代老祖宗;每条弧始点和终点分别是父和子;每条路径始点是祖先,终点是后裔.出度为0的结点(没有儿子者)称为树叶,否则称为分枝点;分枝点及其所有后裔组成子树(非根的分枝点导出真子树).从树根r到一结点a有唯一有向路径,其长度t称为a的层次(a为第t代孙),有根树各结点层次最大值称为树的高度.,有根树的表示功能,与家谱的作用相似,可用有根树表示复杂组织的层次结构或复杂事物的分类结构,计算机的文件系统等等.在计算机科学中常用有根树表示算术运算式.其中一种作法是:运算对象放在树叶的位置,运算符放在分枝点的位置,每个分枝点上的运算都作用在它的左子树和右子树上,计算次序由路径长度确定,远的优先.,
