运筹学课件2012 第11章 图与网络模型.ppt

《运筹学课件2012 第11章 图与网络模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一章图与网络模型运筹学1第十一章图与网络模型图与网络的基本概念最短路问题最小生成树问题最大流问题最小费用最大流问题2哥尼斯堡七桥问题哥尼斯堡（现名加里宁格勒）是欧洲一个城市，普雷格尔（Pregei）河把该城分成两部分，河中有两个小岛，十八世纪时，河两边及小岛之间共有七座桥，当时人们提出这样的问题：有没有办法从某处（如A）出发，经过各桥一次且仅一次最后回到原地呢？§1图与网络的基本概念3ABCD?只经过各桥一次最后能回到原地吗？4ABCD?只经过各桥一次最后能回到原地吗？5最后，数学家Euler（欧拉）在1736年巧妙地给出了这个问题的答案，并因此奠定了图论的基

2、础，Euler把A、B、C、D四块陆地分别收缩成四个顶点，把桥表示成连接对应顶点之间的边，问题转化为从任意一点出发，能不能经过各边一次且仅一次，最后返回该点。这就是著名的Euler问题。§1图与网络的基本概念6ACBD一笔画问题Euler问题7自然界和人类社会中，大量的事物以及事物之间的关系，常可以用图形来描述。例如，为了反映5个队参加的球类比赛请况，可以用点表示球队，用点间连线表示两个队已经比赛过。这样的例子很多，物质结构、电路网络、城市规划、交通运输、物资调配等也都可以用点和线连接起来的图进行模拟。§1图与网络的基本概念81点、边、无向图点——记为vi边——点

3、之间的联线，记为ei无向图——由点和边构成的图叫无向图，记为G=(V,E)赵(v1)钱(v2)孙(v3)李(v4)陈(v7)周(v5)吴(v6)e1e2e3e4e5点的集合边的集合G=(V,E)V={v1，v2，v3，v4，v5，v6，v7}E={e1，e2，e3，e4，e5}图是由点和线构成，可以反映一些对象之间的关系。图分为无向图和有向图。92点、弧、有向图弧——点之间带箭头的联线，记为ai有向图——由点和弧构成的图叫有向图，记为D=(V,A)赵(v1)钱(v2)孙(v3)李(v4)陈(v7)周(v5)吴(v6)a1a2a3a4a5点的集合弧的集合D=(V,A

4、)V={v1，v2，v3，v4，v5，v6，v7}A={a1，a2，a3，a4，a5，a6，a7，a8，a9，a10}a6a7a9a10a8103无向图中的链、圈、连通图、权、赋权图概念链——在无向图中如果存在一个点、边的交错序列称为联结两点的链。例如：（v1，e1，v2，e3，v3）圈——若链的第一个点和最后一点相同，则称之为圈。例如：（v1，e1，v2，e3，v3，e2，v1）连通图——对于一个无向图G，若任何两个不同的点之间至少存在一条链，则称G是连通图。赋权图——对于一个无向图G的每一条边，如果相应有一个数，则称这样的图为赋权图，该数称为边上的权。赵(v1

5、)钱(v2)孙(v3)李(v4)陈(v7)周(v5)吴(v6)e1e2e3e4e5114有向图中的路、回路、权、赋权图、容量、网络概念路——在有向图中如果存在一个点、弧的交错序列称为联结两点的路，例如：（v1，a10，v5，a8，v7，a9，v4）回路——若路的第一个点和最后一点相同，则称之为回路（v1，a1，v2，a3，v3，a2，v1）赋权图——对于一个有向图D的每一条弧，如果相应有一个数，称这样的图为赋权图，该数称为弧上的权。如果在赋权有向图D中指定一点为发点（记为vs），指定另一点为收点（记为vt），其余的点称为中间点，并把D中的每一条弧的赋权数称之为弧的

6、容量，这样的赋权有向图就称之为网络赵(v1)钱(v2)孙(v3)李(v4)陈(v7)周(v5)吴(v6)a1a2a3a4a5a6a7a9a10a812无向图和有向图的联系和区别无向图：点、边、链、圈、权、赋权无向图、连通图有向图：点、弧、路、回路、权（容量）、赋权有向图（网络）无向图是有向图的特例13最短路问题是网络理论中应用最广的问题之一。许多优化问题可以是这个模型，如设备更新、管道铺设、线路安排、厂区布局等。图论方法比较有效。前面我们用动态规划方法解决了一个赋权无向图的最短路问题。求解最短路的Dijkstra算法最短路问题是对一个赋权有向图D中指定的两个点vs

7、和vt找到一条从vs到vt的路，使得路上所有弧的权数的总和最小，这条路上所有弧的权数的总和被称之为从vs到vt的距离。§2最短路问题14本算法由Dijkstra于1959年提出，可用于求解指定两点间的最短路，或从指定点到其余各点的最短路。适用情况：适用于赋权有向图，且每条弧的权数都大于0的情况，目前被认为是求无负权网络最短路问题的最好方法Dijkstra算法也称为双标号法。即对图中的点vj赋予两个标号(lj，kj),第一个标号lj表示从起点vs到vj的最短路的长度，第二个标号kj表示在vs到vj的最短路上vj前面一个邻点的下标，从而找到vs到vt的最短路及vs与v

8、t的距离。