运等学课件 1 第八章 制作;北京理工大学吴祈宗等
运筹学课件 第八章 图与网络分析 制作：北京理工大学 吴祈宗等
第八章图与网络分析 本章内容重点 图的基本概念与基本定理 树和最小支撑树 最短路问题 网络系统最大流冋题 网络系统的最小费用最大流问题 中国邮递员问题
2 第八章 图与网络分析 图的基本概念与基本定理 树和最小支撑树 最短路问题 网络系统最大流问题 网络系统的最小费用最大流问题 中国邮递员问题 本章内容重点
引 图论应用非常广泛 控制论,信息论,工程技术,交 通运输,经济管理,电子计算机等领 城 科学研究,市场和社会生活中的 许多问题,可以用图论的理论和方法 来加以解决。 例如,通信线路的架设,输油管 道的铺设,铁路或者公路交通网络的 租而同
引 言 图论应用非常广泛： 控制论，信息论，工程技术，交 通运输，经济管理，电子计算机等领 域； 科学研究，市场和社会生活中的 许多问题，可以用图论的理论和方法 来加以解决。 例如，通信线路的架设，输油管 道的铺设，铁路或者公路交通网络的 合理布局
3引 将复杂的工程系统和管理问 题用图的理论加以描述,可以 解决许多工程项目和管理决策 的优化问题。 图论越来越受到工程技术 人员和经营管理人员的重视
4 引 言 将复杂的工程系统和管理问 题用图的理论加以描述，可以 解决许多工程项目和管理决策 的优化问题。 图论越来越受到工程技术 人员和经营管理人员的重视
引 1736年瑞士科学家欧拉发表 了关于图论方面的第一篇科学论文, 解决了著名的哥尼斯堡七座桥问题。 德国的哥尼斯堡城有一条普雷 格尔河,河中有两个岛屿,河的两 岸和岛屿之间有七座桥相互连接 如图8-1a所示
5 引 言 1736年瑞士科学家欧拉发表 了关于图论方面的第一篇科学论文， 解决了著名的哥尼斯堡七座桥问题。 德国的哥尼斯堡城有一条普雷 格尔河，河中有两个岛屿，河的两 岸和岛屿之间有七座桥相互连接， 如图8-1a所示