运筹学6-1.ppt

* 第六章 网络模型 网络模型：应用图论理论与方法解决具有网络性质 的管理决策问题的数学模型。它在许多 经济活动中有广泛的应用。 6.1 图论基本知识 6.2 网络中的流 6.3 最短路和最小费用流 6.4 网络计划方法（选讲） 6.5 网络的两个应用实例 链接 链接 链接 链接 链接 6.1 图论基本知识 1. 两个图论实例 例1 著名的哥尼斯堡七桥问题：(P155) 18世纪的哥尼斯堡城中有一条河，河的两岸与河中的 两个小岛有7座桥彼此联接，问一个步行者能否通过每座 桥一次且仅一次就能返回原出发地？ C A B D 问题转化为：能否从任何一个顶点（A，B，C，D） 出发，恰好经过每条边一次而返回原地？ 1736年欧拉证明了否定的答案。 B C A D 例3 （最短路 P156） 下图是一张石油流向管网示意图，A 表示石油开采地， H 为石油汇集站，B，C，D，E，F 表示可供选择的石油 流动加压站，数字为两地距离（管长），问如何选择管 线，使将油从 A 送到 H 所需油管最短？ A B C D E F H 6 2 4 8 6 4 12 2 3 1 2 图 6.3 2. 图的基本概念 (2) 多重图：含有多重边的图称为多重图 简单图：无环无多重边的图称为简单图，本章的图均 指简单图。 (3) 子图： 子图。 支撑子图。 (4) 有向图： 例如 图6.3 的石油流向图，即为有向图。 (5) 链： 无向图 圈。 (6) 路： 闭回路。 (7) 连通图： 连通图 不连通图 (8) 赋权图： 6.1.2 树与最小支撑树 1. 树及其性质： (1) 树 (2) 树的性质： 1 树中任何两点有且仅有一条链 2 在树的任何两点间增加一条边，得到唯一的一个圈。 3 在树中去掉任何一条边后，图不连通。 4 树中顶点个数=边数+1 2. 支撑树： 支撑树的含义：即在G中修去一些边，使之成为连通 无圈图。 3. 图 G 有支撑树的充要条件是 G 连通。 证明 必要性: 充分性（破圈法证明）： (1) 如G不含有圈，则G自身是一棵支撑树。 (2) 如G含有圈，在G的圈上去掉一条边，则该圈被破坏， 形成新的支撑子图G，返回(1). (3) 经有限次破圈后，必产生G的无圈连通子图。 注意 充分性证明给出了求支撑树的计算方法 破圈法。 4. 例4 （P158）用破圈法求图6.5 (a) 的一棵支撑树。 解 取圈及破圈流程图如下： 随便去掉 一条边 图6.5 5. 最小支撑树： 6. 最小支撑树的求法 ---- 去掉最大边的破圈法： 方法与求支撑树类似，只是在每次去边破圈时， 去掉圈中权数最大的边。 例求图6.8(a)的最小支撑树(架设广播线路的最优方案) 2 2 3 4 6 5 4 4