第八章图与网络分析 本章内容重点 图的基本概念与基本定理 树和最小支撑树 最短路同题 网络系统最大流问题 网络系统的最小费用最大流问题 中国邮递员问题
2 第八章 图与网络分析 图的基本概念与基本定理 树和最小支撑树 最短路问题 网络系统最大流问题 网络系统的最小费用最大流问题 中国邮递员问题 本章内容重点
引 图论是应用非常广泛的运筹学分支, 它己经广泛地应用于物理学控制论,信息 论,工程技术,交通运输,经济管理。电 子计算杋等各项领域。对于科学研究,市 场和社会生活中的许多问题。可以同图论 的理论和方法来加以解决。例如,各种通 信线路的架设.输油管道的铺设,铁路或 者公路交通网络的合理布局等问题.都可 以应用图论的方法.简便、快捷地加以解 决
3 引 言 图论是应用非常广泛的运筹学分支， 它已经广泛地应用于物理学控制论，信息 论，工程技术，交通运输，经济管理，电 子计算机等各项领域。对于科学研究，市 场和社会生活中的许多问题，可以同图论 的理论和方法来加以解决。例如，各种通 信线路的架设，输油管道的铺设，铁路或 者公路交通网络的合理布局等问题，都可 以应用图论的方法，简便、快捷地加以解 决
引 随着科学技术的进步,特别是电子 计算杋技术的发展。图论的理论得了 更进一步的发展,应用更加广泛。如果 将复条的工程系统和管理问题用图的理 论加以描述。可以解决许多工程项目和 管理决策的最优问题。因此,图论越来 越受到工程技术人员和经营管理人员的 重视
4 引 言 随着科学技术的进步，特别是电子 计算机技术的发展，图论的理论获得了 更进一步的发展，应用更加广泛。如果 将复杂的工程系统和管理问题用图的理 论加以描述，可以解决许多工程项目和 管理决策的最优问题。因此，图论越来 越受到工程技术人员和经营管理人员的 重视
引 1736年瑞士科学家欧拉发表 了关于图论方面的第一篇科学论 文,解决了著名的哥尼斯堡七座 桥冋题。德国的哥尼斯堡城有 条普雷格尔河,河中有两个岛屿, 河的两岸和岛屿之间有七座桥相 互连接,如图8.1a所示
5 引 言 1736年瑞士科学家欧拉发表 了关于图论方面的第一篇科学论 文，解决了著名的哥尼斯堡七座 桥问题。德国的哥尼斯堡城有一 条普雷格尔河，河中有两个岛屿， 河的两岸和岛屿之间有七座桥相 互连接，如图8.1a所示
引 B D 图8.1a
引 言 A B 图8.1 a A B C D