数学实验12-图.ppt

数学实验第十二章图的模型及算法初步,云南大学信息学院通信工程系宗容,1,第十二章绪论,12.1导言12.2一种表示工具图12.3图的矩阵表述方法12.4算法12.5实验,2,12.1导言,图的研究对象网络，网络优化可见网河道网、灌溉网、公路网、铁路网、电话线网、计算机通讯网、输电线网不可见网各种关系网，如各种状态转移关系、事物的相互冲突关系、工序的时间先后顺序基本的网络优化问题：最短路径、最小生成树、最大流、最小费用流解决方法：线性规划、网络分析本实验目的：掌握如何建立图模型了解图存储结构，学会图的表示与矩阵表示之间的的转化对算法及其复杂性建立初步认识，并树立算法有效性观点,3,12.2一种表示工具图,18世纪东普鲁士哥尼斯堡被普利格尔河分为四块，通过七座桥连接。问题：一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点结果：没有人能够做到,一、七桥问题,4,七桥问题,1736年，著名数学家欧拉(Euler)证明了他的猜想。方法：将南北两岸和两个岛A,B,C,D抽象成四个点，将连接这些陆地的桥用线段表示结果：将问题转化为是否存在从某点(顶点)出发经过每条线(边)一次且仅一次最终回到出发点的路线,5,七桥问题,该问题是欧几里德几何学没有研究过的问题。这里引出的图形、线段的长短、曲直、顶点的准确位置都无关紧要，重要的是点线之间的连接关系。欧拉指出：一个线图中存在通过每边一次且仅一次回到出发点的路线的充要条件是：1）图要是连通的；2）与图中每一顶点相连的边必须是偶数条结论：七桥问题无解,6,二、图的概念和术语,1、图：图G由集合V(G)和E(G)组成，记为G=(V,E)V(G)顶点(图中结点)的非空有穷集合E(G)边的有穷集合(相关顶点的偶对称为边),通常用V，E分别表图的顶点集、边集，图G可用(V，E)表示。V=a,b,c,d，E=(a,b)，(a,c)，(a,d)，(b,c)，(b,c)，(b,d)，(b,d)。,7,图的概念和术语,2.有向图(directedgraph)：图中的边是顶点的有序对有向边，又称为弧，用尖括号表示从vi到vj的一条弧Vi边的始点(尾顶点)Vj边的终点(头顶点)3.无向图(undirectedgraph)：图中的边是顶点的无序对无向边，用圆括号表示（vi,vj）顶点vi与vj相连的一条边图中顶点a,b,c,d和边的端点对为：e1=(a,b)，e2=(a,c)，e3=(a,d)，e4=(b,c)，e5=(b,c)，e6=(b,d)，e7=(b,d),8,图的概念和术语,顶点与边的几个术语：1)若边e的端点为u，v，则称e与顶点u,v相关联2)若顶点u,v之间有边相连，则称u与v相邻3)若边e1，e2与同一顶点相关联，则称相邻4)端点相同的两边称为重边两端点为同一个点的一条边称为环既有有向边又有无向边的图称为混合图,9,图的概念和术语,4.子图：图G=(V,E)，G=(V,E)，若V(G)V(G)，且E(G)E(G)，则称G是G的子图简单图：无重边，无环的图完全图：任意两顶点都有边相连的图,10,图的概念和术语,5.顶点的度TD(vi)：与该顶点相关联的边的数目对有向图，把以顶点v为尾的弧的数目称为顶点v的出度，即OD(vi)（或d+(vi)）把以顶点v为头的弧的数目称为顶点v的入度，即ID(vi)（或d-(vi)）顶点的度：TD(vi)=ID(vi)+OD(vi)若图G有n个顶点，e条边或弧，则,11,图的概念和术语,6.路径：从Vp经过Vi1,Vi2,Vin到Vq，则称该顶点序列为从顶点Vp到顶点Vq的一条路径路径长度：定义为路径上边的数目简单路径：如果一条路径上的顶点除Vp和Vq可以相同外，其它顶点都不同，则称此为一简单路径回路(或环)：Vp=Vq的简单路径,12,图的概念和术语,7.连通图：无向图G中，从vi到vj有一条路径，则称vi到vj是连通的若图G中任意两个顶点vi和vj(vivj)都是连通的，则称此无向图G为连通图一个无向图的连通分量定义为此图的极大连通子图强连通图：在有向图G中，任意两个顶点vi和vj(vivj)都连通，即从vi到vj和从vj到vi都存在路径，则称该图G为强连通图。有向图G中的极大强连通子图称为G的强连通分量,13,图的概念和术语,8.网络或带权图：图中的每一条边附加一个数作为权的图（赋权图）若给每条边赋予一个或多个实数,14,三、图的应用1.古典过河问题,问题：设有n个正常人和n个精神病患者要过一条河。现只有一条能容纳C（C2n）人的小船，为防止患者伤害正常人，要求无论在河岸的哪一边正常人的个数不得少于患者的个数（除非正常人个数为0）。又设每个人都会划船，试设计一个过河的最佳方案（小船来回次数最少）。问题复杂，先构造出相应的数学模型。解：用三元组(x,y,t)表示渡河过程中的某个状态x起始岸上正常人的个数y起始岸上患者的个数t小船的位置,15,古典过河问题,构造一个图图中的每一个顶点代表一个合法的状态，不难得出合法状态下，(x,y,t)必须满足：x=0，orx=n，orx=y图中的边则表示该边所依附的两个顶点（即两个合法状态）间可由一次划船而相互转换例，当n=2,C2时，各合法状态及其转换如图所示(0,2,0)(0,2,1)(2,2,1)(2,0,0)(2,1,1)(0,1,0)(0,0,0)(1,1,0)(1,1,1)(2,1,0),16,古典过河问题,可见，通路的最佳方案不唯一上面过河方案的求解就转换成一个图的搜索问题，及搜索一个图，找出从起始顶点(n,n,1)到目的顶点(0,0,0)的一条包含边数最少的通路，若无，则给出无解的信息。,17,3.田径赛的时间安排问题,问题：设某校的田径赛共设六个项目的比赛：跳高、跳远、标枪、铅球、100m、200m，规定每个选手至多参加三个项目的比赛，现有五名选手报名参赛，选手所选项目如下表所示，要求设计一个竞赛日程安排表，使在尽可能短的时间内安排完比赛。,18,2.田径赛的时间安排问题,设计一个图，图中顶点代表竞赛项目，在所有的两个不能同时进行的比赛项目之间连上一条边。显然，同一选手选择的几个项目不能同时比赛，因此该选手所选择的项目中应该两两有边相连，可得如图所示的模型。,19,田径赛的时间安排问题,竞赛项目的时间安排问题可以抽象为对该无向图进行“着色”操作，即使用尽可能少的颜色去给图中每个顶点着色，使得任意两个有边相连接的相邻顶点着上不同色。,每个颜色表示一个比赛时间，着同一色的顶点可以安排在同一时间内竞赛。只要安排4个不同时间段竞赛即可。,20,21,22,23,24,25,26,27,12.3图的矩阵表示方法,邻接矩阵关联矩阵边矩阵,28,1、邻接矩阵,无向图的邻接矩阵：A=(aij)nn，其中,29,有向图邻接矩阵,有向图，其邻接矩阵A=(aij)nn中的元素aij取为vi指向vj的有向边的数目，图中的有向图的邻接矩阵为,12345,12345,30,网络图的带权邻接矩阵,A=(aij)nn，其中aij取为vi指向vj的有向边上的权。当无边时取为，对角线上的元素为0。,31,2、关联矩阵,无向图的关联矩阵：M(mij)nm，其中,32,3、边矩阵、边权矩阵,边矩阵：定义一个2m的矩阵E，第一、二行分别存放边的起点和终点。若第i条边ei的起点和终点分别为vj，vk，则E(1，i)=j，E(2，i)k,对加权图，只需增加一行来存放各条边上的权，这样的矩阵称为边权矩阵。,33,12.4算法,算法算法定义算法特性算法评价算法分析算法的时间复杂性分析时间复杂度量级比较算法的空间复杂性分析P，NPC与NPH问题浅说,34,1、算法,现代社会，许多问题的解决都离不开计算机程序我们不仅需要算法，而且更需要好的算法。但有些算法可能花费很长时间例如：用行列式的定义来求一个20阶行列式的值，即使是每秒l000万次的计算机也要花大约15万年的时间。从定义出发求n阶行列式的值的算法不可取，它虽然正确，但是无效。故寻找一个问题的有效算法非常重要。如何才能简便地判断一个算法的有效性呢?在什么情况下一个问题找不到有效算法来求出正确解？,35,(1)算法定义,算法是解决某一特定类型问题的有具体步骤的方法。表述一个算法一般有两种方法：步骤描述框图,36,(2)算法特性,一个算法应该包含5个特性有穷性：一个算法必须在执行有限步之后结束确定性：算法的每一步必须是确切地定义的，无二义性。对于每种情况，有待执行的运算必须被严格和清楚地规定可行性：算法应该是可行的，即算法中描述的运算都是相当基本的，他们都是可以通过已经实现的基本运算执行有限次来实现的输入：一个算法有0个或多个输入。他们在算法开始之前对算法给定的量。这些输入取自于特定的集合输出：一个算法有1个或多个输出。它们是同输入有某种特定关系的量。,37,(3)算法评价,求解一个问题可以有多种算法，判断一个算法的好坏主要有以下标准：正确性能满足具体问题需求，反映求解问题对输入、输出和加工处理等的需求可读性便于阅读，利于理解和求解健壮性具有差错和处理功能效率算法运行对资源占用的多少-时间、空间,38,算法效率常用方法,在算法是“正确”的前提下，对算法在计算机上执行耗时和所占空间的分析，常常是人们对算法进行评估和选择的重要依据。确定算法效率的一种常用方法为：把算法用某种高级程序语言编写成程序在特定计算机上输入选定的数据运行测量实际运行时间但它反映计算机系统的综合效率，并非单纯算法效率,39,2、算法的时间复杂性分析,1)时间复杂度用一个整数表示一个问题输入数据量的大小(或输入长)，称为问题的规模。例如，行列式的大小可用其阶数n来度量，因此n就是“求n阶行列式值”这个问题的规模；图问题的规模就是其边数或顶点数。一个算法的时间复杂废可以简单地定义为：从输入数据到计算出结果所需的时间，它是问题规模(或输入长)n的函数，记为T(n)。,40,时间复杂度T(n),同一算法的计算机执行时间与计算机型号、程序语言及程序员的技能等等有关因此，这个时间无法精确度量，我们需要基于算法本身来确定算法的时间复杂度T(n)，而不受机型以及这个算法如何编码等等因素的影响.,41,度量T(n)的一个较恰当的方法是，计算这个算法所需的基本操作，这些基本操作包括加、减、比较、乘、除、交换存储位置，更粗略、更宏观地，我们计算这个算法必须执行的步骤数目，它是实例输入长的函数，,42,n-问题的规模(输入长)，第一句的计算时间为一个常数c1，后面的比较、赋值语句要重复n次，所花时间不超过n的常数倍，即c2n。总的计算时间不超过c1c2n，这是一个与n同阶的量，即有c1+c2nO(n)，这里的“O”表示数量级，读作“n阶”，我们称O(n)为这个算法的时间复杂度。,例如，求n个数最大者的一个算法如下max-999999fori=1：nifnumber(i)maxnmaxnmumber(i)endend,记T(n)为这个算法的时间复杂度。通常记为:T(n)=O(n),43,若存在正数C和n0，使当nn0时，一个算法的执行时间T(n)Cf(n)，则称该算法花了f(n)阶的时间，记为T(n)O(f(n)。例：对下面三个简单的程序段，求时间复杂度,1）x=x+12）fori=1:nx=x+1,3）fori=1:nforj=1:nx=x+1end,end,时间复杂度分别是O(1)，O(n)，O(n2),44,45,46,47,2、计算复杂性函数量级的比较,定义:设有两函数f1(n)与f2(n)，令,1)若0O(f2(n)显然有O(1)O(Logn)O(n)O(n2)O(n3)0(2n)O(n!),48,49,50,空间复杂度,类似于算法的时间复杂度，以空间复杂度作为算法所需存储空间的耗费的度量记为：S(n)=O(f(n)空间单位一般规定为一个简单变量（如整型、字符型等）所占存储空间的大小。其中n问题的规模，f(n)算法处理的数据所需的存储空间与算法操作所需辅助空间之和在分析空间开销时，除关心“静态”分配空间外，还特别注意“动态”申请的空间和递归调用带来的空间开销,51,3、P，NPC与NPH问题浅说,存在许多还没找到有效算法的问题。如其中最著名的要数图论中的“旅行推销员问题”，简称“TSP”,即“已给一个n个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。这些问题称为NP难题(NPHard或NPH)迄今为止，这类问题中没有一个找到有效算法目前倾向于接受NP完全问题(NPcomplet或NPC)和NP难题不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。,52,P，NPC与NPH问题浅说,判定问题：其答案不是“是”就是“否”的问题如，一个图的两顶点之间存在路径吗?判定问题有三类：P，NP和NPC。P类：已有多项式时间算法的判定问题；NP类：已有指数时间算法的判定问题，包括P类；NPC类：是NP的一个子集，且其中每一个问题均能由NP中的任何问题在多项式时间内转化而成。问题A能在多项式时间内转化为问题B，可理解为：问题A有一个算法以问题B的算法为子程序，当把每次对B算法的调用看作一个基本操作(只花常数时间)时，A的这个算法是多项式时间的。,53,P，NPC与NPH问题浅说,在NPC问题之外还有一些问题，其难度与NPC相当或难度超出NPC，这就是NPH问题。NPH类：若问题A不属于NP类，已知某一NPC问题可在多项式时间之内转化为问题A，则称A为NP难题。例如，“TSP”是NPH问题。,54,注意,1）上述这些还不是严格定义，要准确说明P，NP和NPC问题的定义需借助确定型图灵机(deterministicturingmachines)和非确定型图灵机的概念。在某些文献中也将“NP难题”与“NP完全问题”混用。3）NPC类问题是NP类问题中最因难的一类问题，若NPC类中一个问题有多项式时间算法，则NP类中所有问题皆有多项式时间算法。4）迄今为止，已证明为NPC类的问题愈千个。其中，比较著名的有：哈密尔顿路径问题、图的着色问题、独立集、顶点覆盖问题、团的问题、三维匹配问题