运筹学基础图论方法

1、第六章 图论方法【引例1】Knigsberg七桥问题 在Knigsberg城郊的Pregerl河上有两个小岛，小岛和河两岸的陆地由7座桥相连（如图a），问题是如何从河岸或岛上的某一个位置出发，能经过7座桥正好各一次，最后回到出发地。 将图抽象，用4个点代表4个被河隔开的陆地（两岸和岛屿），把桥表示为连接两个陆地之间的边，则得到图b所示的图，从而问题变为如何从图中的某个点出发，经过所有的边正好一次，最后回到这个点。 【引例2】 某河流中有几个岛屿，从两岸至各岛屿及岛屿之间的桥梁如图。在一次军事行动中，问至少炸断几座桥，才能完全切断A与F的交通联系？ADBCDEFAFDECB2(0)1(0)3(0

2、)1(0)2(0)1(0)2(0)1(0)1(0)6.1图的基本概念与模型 图是反映研究对象之间相互关系的一种工具。是在纸上用点和线画出的各种各样的示意图。太原石家庄保定灵丘原平天津塘沽通县秦皇岛密云承德北京张家口怀柔甲乙丙丁戊 图的最基本的要素是点以及点与点之间的一些连线，点表示我们要研究的对象，线表示对象之间的某种特定关系。 如图中点和线赋与具体的含义和权重，称为网络图。图的名词和基本概念边：若点与点之间的连线没有方向，称为边。如e1=v1, v2, e10=v4, v4，v1, v2称为e1的端点，e1称为v1,v2的关联边， v1,v2称为点相邻， e1,e2称为边相邻v1e1v2v3

3、v4v5v6e2e3e4e5e6e7e8e9e10环：如果边的两个端点相重，称该边为环，如e10；如果两个端点之间的边多于一条, 称为具有多重边，如v2, v4 ,无环，无多重边的图为简单图。甲乙丙丁戊弧：若点与点之间的连线有方向，称为弧，由此构成的图为有向图。图的名词和基本概念圈：若起始点和终点是同一个点的链称为圈。例如(v1 ,e1 ,v2 , e2 ,v4 ,e3 ,v3 ,e4 ,v1 ) 。v1e1v2v3v4v5v6e2e3e4e5e6e7e8e9e10链：是一个点、边交错序列, 如（v1 ,e1 ,v2 ,e2 ,v4 )路：如果链中每个项点都不相同, 则称为路，如（v1 ,e1

4、 ,v2 ,e2 ,v4 )回路：若起始点和终点是同一个点的路称为回路。连通图：一个图中，任意两个顶点至少存在一条链，则称这样的图为连通图。否则称为不连通的。v1v2v3v4v5v6e2e4e5e6e7e8e1e3v7v8e9e10图的名词和基本概念v1v2v3v4v5v6e2e4e5e6e7e1e3悬挂节点: 次为1的点称为悬挂节点: 次：与一个点相关联的边的数目称为次, 如v1 的次为2， v5的次为3，次为奇数的点称为奇点，次为偶数的点称为偶点，次为0的点称为孤立点，如v6利用图可以对象之间的关系例：有甲、乙、丙、丁、戊、己六名运动员参加A、B、C、D、E、F六个项目的比赛。打对号的是各

5、运动员参加比赛的项目，问六个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。ABCDEFACBFED6.2 树图和图的最小部分树一、树的性质例如性质1：任何树至少有一个悬挂节点性质2：具有n个顶点的树的边恰好为(n-1)条性质3：任何具有n个顶点、(n-1)条边的连通图是树图。树图的任意两个点之间有一条且仅有一条唯一的通路，是最脆弱的连通图树：一个无圈的连通图称为树。例：树的形成已知在五个城市间架设电话线，要求任何两个城市都可以通话（允许通过其它城市），并且电话线的条数最少。方案一不连通方案三方案二有圈树问题：如何构建才能是最短路径v1v2v3v4v5v1v2v3v4v5v1v

6、2v3v4v5v1v2v3v4v5二、最小树杈问题最小树杈问题是关于在一个网络中，从一个起点出发到所有点，找出一条或几条路线，以使在这样一些路线中所采用的全部支线的总长度是最小的，或铺设费用最少。求图的最小树杈问题的方法有“破圈法”和“避圈法”。破圈法v1v2v3v5e2e3e5e1e6e7e8e4v4v1v2e1v3e2e4v4v5e6避圈法破圈法(克鲁斯喀尔法)例：已知连接五个城市的公交线路图，在要在五个城市间架设电话线，为了便于维修要求电话线必须沿公路架设，并且电话线总长度最小。此为最小树杈v1v2v3v4v52520109151230破圈法：任选一个圈，从圈中去掉杈最大的一条边。在余下

7、的图中重复这个步骤，直到得到一连通的不含圈的图为止。最小线路长度为：20+15+10+9=54避圈法(普赖姆法)避圈法：开始选一条杈最小的边，以后每一步中，总从未被选取的边中选一条杈尽可能小，且与已选边不构成圈的边。此为最小树杈，最小线路长度为54v1v2v3v4v52520109151230又例在住宅小区安装供水管道。求最小线路。1.供水管道的阀门27354630070010002001100900600100500400600破圈法(克鲁斯喀尔法)1.供水管道的阀门2735463007001000200110090060010050040011001000700600600600此为最小树

8、杈，最小线路长度为2400避圈法(普赖姆法)1.供水管道的阀门27354630070010002001100900600100500400600345672此为最小树杈，最小线路长度为2400练习：求最小树杈655172344v1v2v3v4v5v6破圈法答案655172344v1v2v3v4v5v6避圈法答案v3v21v42v53v641v2v3v4v5v6练习：求最小树杈25312234533232226.3 最短线路问题当通过网络的各边所需时间、距离或费用为已知时，找出从入口到出口所需的最少时间、最短距离或最少费用的路径问题，称做网络的路线问题。 本节主要介绍最

9、短路线问题。方法以是从终点开始逐步逆向推算1003009-106-9-105004-6-9-106501-4-6-9-101508-103757-8-104005-8-106002-6-9-106003-5-8-1028453610040035027517525017915017522515010020030020027520010416910最短路线为650一、起点到终点的最短距离例2答案：1-3-6-7路长1212473527 256436 2 735-766-7 684-6-7102-4-6-72-5-7103-6-7121-3-6-71367练习：求1到7的最短路线1237441567

10、 45621568 5 1237441567 45621568 565-776-5-7124-6-5-7113-6-5-73-5-7122-3-6-5-72-3-5-7161-2-3-5-71-2-3-6-5-712357632157答案：1-2-3-5-7或1-2-3-6-5-7路长16利用EXCEL求起点到终点的最短路径第一步：建立各结点间的距离矩阵利用EXCEL求起点到终点的最短路径第二步：建立各结点间的通道限制矩阵利用EXCEL求起点到终点的最短路径第三步：定义最小路线运行方案 第四步：利用规划求解二、任意两点间最短距离的矩阵算法上述算法提供了求图中某一点到其它点的最短距离。但实际问题

11、中往往要求网络任意两点间的最短距离，如应用上述算法，会很麻烦，下面介绍求任意两点间最短距离的矩阵算法。例：计算下图中任意两点间距离。124735 27 256436 2 7 61解：定义dij为图中任意两点间的距离构造矩阵D（1），使则矩阵D（1）给出了网络中任意两点之间直接到达和包括一个中间点时的最短距离。由得到的矩阵D（1）继续构造矩阵D（2），使则矩阵D（2）给出了网络中任意两点之间直接到达和包括一个至三个中间点时的最短距离。一般地，有则矩阵D（k）给出了网络中任意两点之间直接到达和包括一个、两个、到(2k-1)个中间点时比较得到的最短距离。设网络图中有p个点，则一般计算不超过D（k），其中k满足应用若图中v1, v2, v3, v4, v5, v6, v7,为七个村子，决定联合办一所小学，已知各村小学生人数为30、40、25、20、50、60、60，小学则应建在哪一个村子，使小学生走的总路程最短。选择在第6个村子里建小学，小学生走的总路程最短。30402520506060EXCEL求任意两点间的最短距离单元格G24输入公式“=MIN($B14:$H14+TRANSPOSE(G$1