《运筹学基础图论方法1》由会员分享，可在线阅读，更多相关《运筹学基础图论方法1（34页珍藏版）》请在金锄头文库上搜索。
1、第六章 图论方法,【引例1】Knigsberg七桥问题,在Knigsberg城郊的Pregerl河上有两个小岛，小岛和河两岸的陆地由7座桥相连（如图a），问题是如何从河岸或岛上的某一个位置出发，能否经过7座桥正好各一次，最后回到出发地。,将图抽象，用4个点代表4个被河隔开的陆地（两岸和岛屿），把桥表示为连接两个陆地之间的边，则得到图b所示的图，从而问题变为如何从图中的某个点出发，经过所有的边正好一次，最后回到这个点。,【引例2】,某河流中有几个岛屿，从两岸至各岛屿及岛屿之间的桥梁如图。在一次军事行动中，问至少炸断几座桥，才能完全切断A与F的交通联系？,6.1 图的基本概念与模型,图是反映研究对
2、象之间相互关系的一种工具。是在纸上用点和线画出的各种各样的示意图。,图的最基本的要素是点以及点与点之间的一些连线，点表示我们要研究的对象，线表示对象之间的某种特定关系。,如图中点和线赋与具体的含义和权重，称为网络图。,图的名词和基本概念,边：若点与点之间的连线没有方向，称为边。如e1=v1, v2, v1, v2称为e1的端点，e1称为v1,v2的关联边， v1,v2称为点相邻， e1,e2称为边相邻,环：如果边的两个端点相重，称该边为环，如e10；如果两个端点之间的边多于一条, 称为具有多重边，如v2, v4 ,无环，无多重边的图为简单图。,弧：若点与点之间的连线有方向，称为弧，由此构成的图
3、为有向图。,图的名词和基本概念,圈：若起始点和终点是同一个点的链称为圈。例如(v1 ,e1 ,v2 , e2 ,v4 ,e3 ,v3 ,e4 ,v1 ) 。,链：是一个点、边交错序列, 如（v1 ,e1 ,v2 ,e2 ,v4 ),路：如果链中每个项点都不相同, 则称为路，如（v1 ,e1 ,v2 ,e2 ,v4 ),回路：若起始点和终点是同一个点的路称为回路。,连通图：一个图中，任意两个顶点至少存在一条链，则称这样的图为连通图。否则称为不连通的。,图的名词和基本概念,悬挂节点: 次为1的点称为悬挂节点:,次：与一个点相关联的边的数目称为次, 如v1 的次为2， v5的次为3，次为奇数的点称为
4、奇点，次为偶数的点称为偶点，次为0的点称为孤立点，如v6,利用图可以对象之间的关系,例：有甲、乙、丙、丁、戊、己六名运动员参加A、B、C、D、E、F六个项目的比赛。打对号的是各运动员参加比赛的项目，问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。,A,B,C,D,E,F,A,C,B,F,E,D,6.2 树图和图的最小部分树,一、树的性质,例如,性质1：任何树至少有一个悬挂节点,性质2：具有n个顶点的树的边恰好为(n-1)条,性质3：任何具有n个顶点、(n-1)条边的连通图是树图。,树图的任意两个点之间有一条且仅有一条唯一的通路，是最脆弱的连通图,树：一个无圈的连通图称为树
5、。,例：树的形成,已知在五个城市间架设电话线，要求任何两个城市都可以通话（允许通过其它城市），并且电话线的条数最少。,方案一,不连通,方案三,方案二,有圈,树,问题：如何构建才能是最短路径的树最小枝权树问题,接上节、求最小树杈问题,最小树杈问题是关于在一个网络中，从一个起点出发到所有点，找出一条或几条路线，以使在这样一些路线中所采用的全部支线的总长度是最小的，或铺设费用最少。,求图的最小树杈问题的方法有“破圈法”和“避圈法”。,破圈法,v1,v2,e1,v3,e2,e4,v4,v5,e6,避圈法,破圈法(克鲁斯喀尔法),例：已知连接五个城市的公交线路图，在要在五个城市间架设电话线，为了便于维修
6、要求电话线必须沿公路架设，并且电话线总长度最小。,此为最小树杈,破圈法：任选一个圈，从圈中去掉杈最大的一条边。在余下的图中重复这个步骤，直到得到一连通的不含圈的图为止。,最小线路长度为：,20+15+10+9=54,避圈法(普赖姆法),避圈法：从任意一个节点开始，选一条杈较小的边连接，以后每一步中，总从未被选取的边中选一条杈尽可能小，且与已选边不构成圈的边。,此为最小树杈，最小线路长度为54,又例,在住宅小区安装供水管道。求最小线路。,600,破圈法(克鲁斯喀尔法),1.供水管道的阀门,2,7,3,5,4,6,300,700,200,900,600,100,500,400,700,600,60
7、0,600,此为最小树杈，最小线路长度为2400,避圈法(普赖姆法),1.供水管道的阀门,2,7,3,5,4,6,300,700,1000,200,1100,900,600,100,500,400,600,3,4,5,6,7,2,此为最小树杈，最小线路长度为2400,练习：求最小树杈,破圈法答案,6,5,5,1,7,2,3,4,4,v1,v2,v3,v4,v5,v6,此为最小树杈，最小线路长度为15,避圈法答案,v3,v2,1,v4,2,v5,3,v6,4,v1,5,此为最小树杈，最小线路长度为15,练习：求最小树杈,2,5,3,1,2,2,3,4,5,3,3,2,3,2,2,2,6.3 最短
8、线路问题,当通过网络的各边所需时间、距离或费用为已知时，找出从入口到出口所需的最少时间、最短距离或最少费用的路径问题，称做网络的路线问题。,100,300,9-10,6-9-10,500,4-6-9-10,650,1-4-6-9-10,150,8-10,375,7-8-10,400,5-8-10,600,2-6-9-10,600,3-5-8-10,4,1,6,9,10,最短路线为650,一、起点到终点的最短距离,本节主要介绍从起点到终点的最短路线问题。方法以是从终点开始逐步逆向推算,例2,答案：1-3-6-7路长12,1,2,4,7,3,5,2,7,2,5,6,4,3,6,2,7,3,5-7,
9、6,6-7,6,8,4-6-7,10,2-4-6-7,2-5-7,10,3-6-7,12,1-3-6-7,1,3,6,7,练习：求1到7的最短路线,1,2,3,7,4,4,1,5,6,7,4,5,6,2,1,5,6,8,5,6,5-7,7,6-5-7,12,4-6-5-7,11,3-6-5-7,3-5-7,12,2-3-6-5-7,2-3-5-7,16,1-2-3-5-7,1-2-3-6-5-7,1,2,3,5,7,6,3,2,1,5,7,答案：1-2-3-5-7或1-2-3-6-5-7路长16,利用EXCEL求起点到终点的最短路径,第一步：建立各结点间的距离矩阵,利用EXCEL求起点到终点的
10、最短路径,第二步：建立各结点间的通道限制矩阵,利用EXCEL求起点到终点的最短路径,第三步：定义最小路线运行方案,第四步：利用规划求解,二、任意两点间最短距离的矩阵算法,上述算法提供了求图中某一点到其它点的最短距离。但实际问题中往往要求网络任意两点间的最短距离，如应用上述算法，会很麻烦，下面介绍求任意两点间最短距离的矩阵算法。,例：计算下图中任意两点间距离。,解：定义dij为图中任意两点间的距离,构造矩阵D（1），使,则矩阵D（1）给出了网络中任意两点之间直接到达和包括一个中间点时的最短距离。,由得到的矩阵D（1）,继续构造矩阵D（2），使,则矩阵D（2）给出了网络中任意两点之间直接到达和包括
11、一个至三个中间点时的最短距离。,一般地，有,则矩阵D（k）给出了网络中任意两点之间直接到达和包括一个、两个、到(2k-1)个中间点时比较得到的最短距离。,设网络图中有p个点，则一般计算不超过D（k），其中k满足,应用,若图中v1, v2, v3, v4, v5, v6, v7,为七个村子，决定联合办一所小学，已知各村小学生人数为30、40、25、20、50、60、60，小学则应建在哪一个村子，使小学生走的总路程最短。,选择在第6个村子里建小学，小学生走的总路程最短。,30 40 25 20 50 60 60,EXCEL求任意两点间的最短距离,单元格G24输入公式 “=MIN($B14:$H14+TRANSPOSE(G$12:G$18)”后，同时按“Ctrl+Shift+Enter”,EXCEL求任意两点间的最短距离,单元格G35输入公式 “=MIN($B24:$H24+TRANSPOSE(G$22:G$28)后，同时按“Ctrl+Shift+Enter”,
