小李自广西大学营销专业毕业进入利客隆工作前天刚过1年,昨天得到了一个好消息,公司调它到总部做配送调度。小李very,very高兴,说公司很给力,决定一定要做好这份工作。而公司也希望借用小李的学识,以进一步规范企业配送,提高质量,降低成本,在沃尔玛、南城百货等大型超市挤压下争取生存机会。但对小李来说,调度还线年的小李,对公司的规模、布局了如指掌。
长虹街道近年新建了11个居民小区,各小区的大致位置及相互间的道路距离如图所示,单位(100m),各居住小区居民数为:①2000,②3000,③3500,④3700,⑤5000,⑥2800,⑦4500。
政府想在7个小区准备共建一套医务所、邮局、储蓄所等服务设施,应建于哪一居民小区,使对居民总体来说感到方便。
工作组组织考察,从小区①出发,经过各小区(顺序不限),最后到小区⑦再离去,哪条路最近?
图论是应用非常广泛的运筹学分支,它已经广泛地应用于物理学控制论,信息论,工程技术,交通运输,经济管理,电子计算机等各项领域。对于科学研究,市场和社会生活中的许多问题,可以同图论的理论和方法来加以解决。例如,各种通信线路的架设,输油管道的铺设,铁路或者公路交通网络的合理布局等问题,都可以应用图论的方法,简便、快捷地加以解决。
随着科学技术的进步,特别是电子计算机技术的发展,图论的理论获得了更进一步的发展,应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述,可以解决许多工程项目和管理决策的最优问题。因此,图论越来越受到工程技术人员和经营管理人员的重视。
1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文《与位置几何有关的一个问题的解》,解决了著名的哥尼斯堡七座桥问题。17世纪的东普鲁士有一座哥尼斯堡城(现在叫加里宁格勒,在波罗的海南岸),城中有一条普雷格尔河,河中有两个岛屿,河的两岸和岛屿之间有七座桥相互连接,如下图所示。
当地的居民热衷于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地。
为了寻找答案,1736年欧拉把陆地缩为一点,把桥作为连接点的边,将这个问题抽象成图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形,最终回到原点。欧拉在他的论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论中的第一个著名问题。
在实际的生产和生活中,人们为了反映事物之间的关系,常常在纸上用点和线来画出各式各样的示意图。
例有六支球队进行足球比赛,我们分别用点v1…v6表示这六支球队,它们之间的比赛情况,也可以用图反映出来,已知v1队战胜v2队,v2队战胜v3队,v3队战胜v5队,如此等等。这个胜负情况,可以用下图所示的有向图反映出来。
我们就把类似以上的几个例子中通过点和点之间的线来反映实际生产和生活中的某些特定对象之间的特定关系的所构成图形称为图(Graph)。一般来说,通常用点表示研究对象,用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下,图中的相对位置如何,点与点之间线的长短曲直,对于反映研究对象之间的关系,显的并不重要,因此,图论中的图与几何图,工程图等本质上是不同的。
图论中所研究的图,是指反映或描述自然界或人类社会中,大量的事物及事物之间关系的图形。是由点和线组成的。点称为顶点,它的集合用V(Vertex)表示,顶点通常表示有形或无形的事物。线称为边,它的集合用E(Edge)表示,边通常表示事物与事物(点与点)之间的联系或特定的关系。
在图论中,我们只关心两点间是否有联系,至于公路的大小、等级、状况均无关紧要,亦即不考虑线段(边)的长度,点的位置带有随意性,它们并不按比例尺画,如五个镇之间的连接图也可画成右图表示。
定义1:一个图是由点集V={vi}和V中元素的无序对集E={ek}所构成的二元组,记作:G=(V,E),其中vi称为顶点,ek称为边。V表示顶点个数,E表示边的个数。当V和E都是有限集合时,G为有限图,否则,称为无限图。本书只论及有限图。图中所有边都没有方向,称为无向图,否则称为有向图。例如下面图6-3,即为无向图.
关联边:和同一个顶点相连的边,均称为该点的关联边,如图6-4中的e24、e34、e45均是v4的关联边。
相邻点:一条边的两个顶点,称为相邻点,如v2与v4,v4与v5等是相邻点,而v2与v5则不是。
环与多重边:两个顶点相同的边称为环,如e22,两个顶点之间的边数≥2时,叫多重边,如e13,e’13就是二重边。
次:一个顶点v具有关联边的总数称为该顶点的次,记作d(v)(每个环视作两条边),如图6-4。
简单图:无环、无多重边的图称为简单图,如图6-4(a)、(b)、(c),后面如无特殊说明,均指简单图。
子图与支撑子图:在图G=(V,E)中,若V1V,E1E,则图G1=(V1、E1)称为G的子图,如图6-4中的(b)就是(a)的子图。特别地:V1=V,E1E时,称G1是G的支撑子图(生成子图)。如图6-4中(c)、(b)都是(a)的支撑图。
定义2 无向图G=(V,E)中,称某些点及其关联边的交替序列{v1 e1 v2 e2 … en vn }为从v1到vn的一条链,v1、vn分别称为链的始点和终点,链长为n。
若一条链的始点与终点重合,则称为闭链(在无向图中闭链又称为回路),否则,称为开链。点边序列中若只有重复的点而无重复的边,则称为简单链。点边序列中若既没有重复的点也无重复的边,则称为初等链(也称为通路)。
一个图连同定义在其边集上的实函数一起称为一个网络.网络一般是连通图.定义在边集上的实函数称为边的权数记为
它与边(vi,vj)具有一一对应关系,可以用以表达网络上的各种有关性质,如路长、流量、费用等等.网络的图解即在每条边旁标上相应的权数.
所谓网络分析,即对网络进行定性和定量分析,以便为实现某种优化目标而寻求最优方案.这方面的典型问题有:最小树问题,最短路问题,中心问题,重心问题,最大流问题,最小费用最大流问题,网络计划问题,等等.
v6等等。但不同的路线,经过的总长度是不同的。例如,按照第一个线单位,按照第二个路线单位。
1、双标号法(Dijkstra算法),它是在1959年提出来的。目前公认,在所有的权wij ≥0时,这个算法是寻求最短路问题最好的算法。并且,这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。
(1)首先给v1以P标号,P(v1)=0,给其余所有点T标号,T(vj)=+∞( j = 2,3,… 6)
(7) 标出最短路 最短路径是:v1→v2→v3→v5→v4→v6 ,路长10.同
双标号法只适用于所有wij ≥0的情形,当赋权有向图中存在负权时,则算法失效.