图与网络建模

图与网络建模什么是图?图G=G(V,E)，由顶点和边组成，V是一个非空的有限集，称为顶点集，E是边集，E中的任意元素e=uv(其中u，v∈V)称为连接顶点uv的边。图的基本概念环与重边；有限图与简单图关联与相邻；顶点的度邻接矩阵与关联矩阵子图、生成子图路、圈；距离；连通图、连通分支；完全图、正则图、树、二部图、完全二部图、平面图有向图；几个简单的定理定理1：图G的所有顶点的度数和等于边数的2倍。推论：任何图中，奇度点的个数为偶数。定理2：一个图是二部图当且仅当它不包含奇圈。定理3：若最小度δ(G)≥2，则G一定包含圈。最短路问题城市公路网络四通八达，如何选择行车路线，使得从A地到B地行车路程最短？某跨国公司在世界各地都有分公司，如何确定任意两个分公司之间最廉价的航空路线？最短路问题2008年1月底，我国南方出现极端冰雪天气。大量电塔倒塌，输电线路中断。有的城市甚至成为输电孤岛，全城一片黑暗。要恢复供电，这既是一个时间问题，同时也是一个资金问题。城市间供电网络的通讯线路建造费用和时间不同，如何一条费用最少的输电路线？在不考虑资金的情况下，如何确定一条最快的输电路线？赋权图对图G的每一条边e，可赋以一个实数w(e)，称为e的权。图G连同它边上的权称为赋权图。确定一个赋权图的任意两顶点u和v之间的一条具有最小权和的路。Dijkstra算法能确定从一固定点u0到其它各点的最短路。(适用于权为非负值)Dijkstra算法的步骤设|V(G)|=n,若u,v不相邻，取w(uv)=∞0},{;)(,000iuSvluv对;0)(0ul)}()(),(min{)(vuwulvlvlSviii令Step1:令Step2:Step3:}{11iiiuSS设ui+1是使l(v)取最小值的V-Si中的顶点令i=n-1时，停止；若in-1,i=i+1,转Step2选址问题所选地址到最远服务对象的距离最小如：紧急情况的安全出口的位置、居民区的便利超市的位置所选地址到各服务对象的距离总和最小如：小区变电站的位置、仓库的位置、产品的售后服务站的位置设备更新问题企业使用某种设备，每年要决定是继续使用(支付维修费用)，还是购置新设备(支付购置费)。每年的维修费用和购置费用不同。如何制定一个五年内的设备更新计划，使得总的支付费用最小。树——无圈的连通图六个顶点的不同构的树两个特殊的树——路(Pn)和星(Sn)树的一些性质在一棵树中，任意两个顶点均由唯一的路连接。若T是一棵树，则|E(T)|=|V(T)|-1.每一棵非平凡的树至少有两个1度顶点。生成树图G的生成树是指G的生成子图，它同时又是树。每个连通图都包含生成树。Cayley公式用τ(G)表示G的生成树的个数。标号的n个顶点的完全图的生成树共有nn-2个。即2)(nnnKe是连通图G中的一条边，则)()()(eGeGG求生成树的算法深度优先搜索法广度优先搜索法最小生成树在赋权连通图中，总权重最小的树称为最小生成树。连线问题：建造一个连接若干城镇的铁路网络。已知城镇vi和vj之间直通铁路的造价为cij，设计一个总造价最小的铁路网络。具有约束的连线问题：用最小费用建造一个连接若干城市的铁路网络，同时要求某些选定的城市对是直接连接的。Kruskal算法1、选择边e1，使得w(e1)尽可能小。2、若已选定边e1,e2,…,ei，则从E\{e1,e2,…,ei}中选取ei+1，使（1）G[{e1,e2,…,ei+1}]是无圈图；（2）w(ei+1)是满足（1）的尽可能小的权。3、当2不能继续时停止。其它算法删边法——G=(V,E)是赋权图，在保证G连通的情况下删掉G中权最大的边，直到获得G的生成树。破圈法——在赋权图G中任取一个圈，删去其中权最大的边，直至G中没有圈。贪婪算法数据压缩问题在计算机或通信领域，常用二进制编码来表示字符。由于各个字符的使用频率不同，为了节省存储空间和数据传输量。若字符出现的频率较高，则用较短的二进制编码表示；若字符出现的频率较低，则用较长的二进制编码表示。最优二叉树算法(Huffman)最优二叉树检索根树[父结点与子结点；层数]；二叉树；完全二叉树；赋权二叉树；最优二叉树前缀码与Huffman编码Huffman算法给定实数w1,w2,…,wt且w1≤w2≤…≤wt1连接w1,w2为权的两片叶子，得一分支点，其权为w1+w2。2在w1+w2,…,wt中选出两个最小的权，连接它们对应的顶点，得分支点及所带的权。3重复2直到形成t-1个分支点，t片叶子。七桥问题近代图论的历史可追溯到18世纪的七桥问题－－穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。Euler1736年证明了不可能存在这样的路线。Königsberg桥对应的图AACDBBDCEuler定理图G的Euler环游是指经过G的每条边恰好一次的环游。Euler定理：任意的非空连通图G，G中存在一条Euler环游，当且仅当它没有奇度点。七桥问题对应的图的四个顶点全是奇度点，显然不存在Euler环游。中国邮递员问题1962年中国组合数学家管梅谷教授提出了著名的“中国邮递员问题”。一个邮递员从邮局出发，递送邮件，他必须要走过他所管辖的每一条街道至少一次，然后返回邮局。那么如何选择一条尽可能短的路线。中国邮递员问题中国邮递员问题就是在边赋权图G中找出一条权重最小的环游。称为最优环游。若G是Euler图，则G的任何Euler环游都是最优环游。在Euler图中确定Euler环游的好算法——Fleury算法。Fleury算法1、任意选取一个顶点v0，置W0=v0。2、假设迹Wi=v0e1v1…eivi已经选定，那么按下述方法从E\{e1,e2,…,ei}中选取边ei+1（1）ei+1和vi相关联；（2）除非没有别的边可选择，否则ei+1不是Gi=G−{e1,e2,…,ei}的割边。3、当第2步不能再执行时算法停止。中国邮递员问题若G不是Euler图，则G的最优环游将通过某些边超过一次。这个问题可以转化为：给定一个具有非负权的赋权图G，（1）用添加重复边的方法求G的一个Euler赋权母图G*，使得尽可能小。（2）求G*的Euler环游。1973年，J.Edmonds和Johnson给出求解（1）的一个好的算法。)(\)(*)(GEGEeew中国邮递员问题特殊地假设G恰有两个奇度点u和v，G*是用添加重复边的方法得到的G的Euler生成母图。在G中找一条具有最小权的(u,v)路，重复这条路上的每一条边，得到G*。Hamilton圈和货郎担问题图G的Hamilton圈是指包含G的每一个顶点的圈。一个货郎要去若干城镇卖货，然后回到出发地，给定各城镇之间所需的旅行时间后，应怎样计划他的路线，使他能去每个城镇恰好一次而且总时间最短？在一个赋权完全图中，找出一个具有最小权的Hamilton圈。货郎担问题这个问题目前还没有有效的算法——NPC问题求近似解——邻近点算法；最小生成树算法。邻近点近似算法1、任选一顶点v1∈V，置P1=v1,i=12、假设Pi=v1v2…vi已选定，选取vi+1∈V\{v1,v2,…,vi}满足权w(vivi+1)最小。3、若i=n,停止，C=Pn+vnv1即所求；否则i=i+1，转2。有向图有向图D=(V,A)，从u连接到v的弧a，称u是a的尾，v是a的头。基础图、定向图、有向路、有向圈双向连通、弱连通入度、出度竞赛图完全图的定向图称为竞赛图。D的有向Hamilton路是指包含D的每个顶点的有向路。每个竞赛图都有有向Hamilton路。存在一个在竞赛图中求有向Hamilton路的好的算法。支付工钱问题假设一名出版业者有n本不同的书需要印刷装订。他有一台印刷机自己印刷，但需要雇佣工人装订。一本书必须在装订之前印刷，装订工人的工钱是从装订机第一次启动到所有装订完毕，按时间计算。那么这些书以什么样的顺序装订，可以使支付个装订工人的工钱最少？支付工钱问题设印刷第k本书需要的时间为pk，装订第k本书需要的时间为bk，现在要寻找一个书的排列顺序，使得如果书以这样的顺序印刷和装订，在第一本书印刷完成之后装订机保持忙碌而没有空闲时间。构造有向图D=(V,A)，V={1,2,…n}，从顶点i到顶点j有弧当且仅当bi≥pj，这个图是一个竞赛图，存在一条有向Hamilton路。即为印刷顺序。工件排序问题设某台机器必须加工多种工件J1,J2,…,Jn；在一种工件加工完毕之后，为了加工下一种工件，机器必须进行调整。如果从工件Ji到工件Jj的调整时间为tij，求这些工件的一个排序，使得整个机器的调整时间最少。构作具有顶点v1,v2,…,vn有向图D，使得(vi,vj)∈A当且仅当tij≤tji。则D包含一个生成竞赛图。求D的一个有向Hamilton路。其它问题单行路系统的构造：给定一个道路系统，怎样把它改成单行道路系统，而使交通尽可能畅通？——图的定向使其双向连通竞赛参加者的名次的排列：一场网球循环赛中，若干选手两两相互竞赛，得出比赛成绩后，应该怎样排参加者的名次？——T.H.Wei和M.G.Kendall曾给出一个排名方法网络流问题随着中国经济快速的增长，物流业逐渐成为要大力发展的新兴服务产业。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。网络网络N=(D,A,c)、收点y、发点x、中间点I容量函数c(a)网络N中的流是指定义在A上的一个整数值函数f，使得(1)容量约束0≤f(a)≤c(a)，对所有a∈A成立(2)守恒条件f-(v)=f+(v)，对所有v∈I成立从x点流出的总流量等于y点流进的总流量，定义为流值。最大流就是流值最大的流。最大流最小割定理：在任何网络中，最大流的值等于最小割的容量。Ford-Fulkerson最大流标号算法0,)2(jiijfvv上若在弧1给x标号(0,∞),x成为标号未检查点,2取标号而未检查的点vi,对一切未标号点vjijijjicfvv,)1(上若在弧}),(min{)()),(,(ijijijjijfcvlvlvlvv其中标上则给}),(min{)()),(,(jiijjijfvlvlvlvv其中标上则给此时vj成为标号未检查点,vi成为标号已检查点重复上述步骤,若y被标号转到3。否则停止。3找到x到y的一条路,对路上顺向弧)(tijvlf逆向弧)(tijvlf,转到1匹配图G=(V,E)，设M是E的子集，并且M中的任意两条边在G中均不相邻，则称M为G的匹配。若匹配M的某条边与顶点v关联，则称M饱和顶点v，并且称v是M饱和的，否则称v是M非饱和的。若G的每一个顶点均为M饱和的，则称M为G的完美匹配。匹配最大匹配：若G中没有另外的匹配M’，使得|M’|＞|M|，则称M为G的最大匹配。每个完美匹配都是最大匹配。M交错路：边在E\M和M中交错出现的路M可扩路：起点和终点都是M非饱和的M交错路。G的匹配M是最大匹配当且仅当G不含M可扩路。Hall定理设S为图G的任一顶点集，将与S中的顶点相邻的所有顶点的集合称为S的邻集，记为NG(S)。Hall定理：设二部图G=(X,Y)，则G中存在饱和X的每个顶点的匹配，当且仅当|N(S)|≥|S|，对所有X子集S成立。推论(婚姻定理)：若G是k正则二部图(k≥1)，则G有完美匹配。婚姻问题如果一个村子里每一个女孩都恰好认识k个男孩，并且每一个男孩也恰好认识k个女孩，那么每一个女孩都可以嫁给她认识的一个男孩，并且每一个男孩都可以娶一个他认识的女孩。稳定的婚姻问题但这样的安排方法不一定是最好的。假如能找到两对夫妇（如A男-a女和B男-b女），如果彼此都更喜欢对方的配偶，A男更喜欢b女，而b女也更喜欢A男，那么这样婚姻有潜在的不稳定性。用图论匹配理论中Gale-Shapley算