资源描述：
《管理运筹学 第6章 图与网络模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第六章图与网络模型主讲教师：马越峰第六章图与网络模型6.1.图与网络的基本知识6.2.最短路问题6.3.最小树问题6.4.最大流问题哥尼斯堡七桥问题18世纪时，欧洲有一个风景秀丽的小城哥尼斯堡，那里有七座桥。河中的小岛C与河岸A、对岸B各有两座桥相连接，河中两支流之间的陆地D与A、B、C各有一座桥相连接。当时哥尼斯堡的居民中流传着一道难题：一个人怎样才能一次走遍七座桥，每座桥只走过一次，最后回到出发点？大家都试图找出问题的答案，但是谁也解决不了这个问题。这就是著名的七桥问题1857年，哈密尔顿，实心12面体，20个顶点-环球旅行中国邮递员问题例1：有A、B、C、D、E五个球队，它们之
2、间比赛的情况，也可以用图表示出来。已知A队和其它各他队都比赛过一次，B队和A队比赛过，C队和B、D队比赛过，D队和C、E队比赛过，E队和A、C队比赛过。为了反映这个情况，可以用点分别代表这五个队，若两个队之间比赛过，就在这两队相应的点之间联一条线，这条线不过其它的点，如图所示。例2：某单位储存八种化学药品，其中某些药品是不能存放在同一个库房里的。为了反映这个情况要以点v1、v2、…、v8分别代表这八种药品，若药品vi和vj不能存放在同一个库房，则在vi和vj之间联一条线。问最少设几处库房才能安全存放这些药品。§6.1图与网络的基本概念图论中图是由点和边构成，可以反映一些对象之间的关系
3、。如物质结构、电路网络、城市规划、交通运输、信息传递、物资调配等都可以用点和线连接起来的图进行模拟。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图1就是一个表示这种关系的图。(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图2来表示，可见图论中的图与几何图、工程图是不一样的。(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6
4、)陈(v7)e2e1e3e4e5图2a1a2a3a4a14a7a8a9a6a5a10a12a11a13a15(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈图3如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。图（Graph）由点（Vertex）和点之间的连线所构成的集合。不带箭头的连线称为边；带前头的连线称为弧。点和边的集合称为无向图（Undirectedgraph），如图(a)，用G={V，E}表
5、示；点和弧的集合称为有向图（Directedgraph），如图(b)，用D={V，A}表示。(a)(b)链（Chain）前后相继并且方向不一定相同的边序列称为链C={(1,2),(3,2),(3,4)}4231回路（Circuit）起点和终点重合的路径称为回路μ={(1,2),(2,4),(4,1)}回路中各条边方向相同4231路径（Path）前后相继并且方向相同的边序列P={(1,2),(2,3),(3,4)}圈(Cycle)起点和终点重合的链称为圈ρ={(1,2),(2,4),(3,4),(1,3)}圈中各条边方向不一定相同4231连通图任意两个节点之间至少有一条链的图称为连通图
6、24351树(Tree)无圈的连通图称为树树中只与一条边关联的节点称为悬挂节点赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。给了一个图，如果图，使及，则称是的一个支撑子图。v8v2v3v4v5v6v7v1v8v2v4v5v7v8v5要求有连线的药品不能放在一起，只要找出一个点的序列，使放在一起的点互不相邻。§6.2最短路问题最短路问题：对一个赋权的有向图D中的指定的两个点Vs
7、和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。最短路问题是重要的最优化问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管道铺设、线路安排、厂区布局、设备更新等等，而且经常被作为一个基本工具，用于解决其它的优化问题。1.给起点v1以标号(0,s)，表示从v1到v1的距离为02.找出已标号的点的集合I，没标号的点的集合J以及弧的集合3.如果上述
