第八章图与网络分析主要内容：88.1图的基本概念与基本定理S8.2树和最小支撑树S8.3最短路问题88.4最小费用流问题88.5最大流问题88.6网络计划88.7中国邮递员问题88.7指派问题
第八章 图与网络分析 主要内容： §8.1 图的基本概念与基本定理 §8.2 树和最小支撑树 §8.3 最短路问题 §8.4最小费用流问题 §8.5最大流问题 §8.6网络计划 §8.7中国邮递员问题 §8.7指派问题
$ 8.11图的基本概念与基本定理图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法简便、快捷地加以解决
§8.1 图的基本概念与基本定理 图论是应用非常广泛的运筹学分支，它 已经广泛地应用于物理学控制论，信息论， 工程技术，交通运输，经济管理，电子计算 机等各项领域。对于科学研究，市场和社会 生活中的许多问题，可以同图论的理论和方 法来加以解决。例如，各种通信线路的架设， 输油管道的铺设，铁路或者公路交通网络的 合理布局等问题，都可以应用图论的方法， 简便、快捷地加以解决
随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视，关于图的第一篇论文是瑞士数学家欧拉（E.Euler）在1736年发表的解决“哥尼
随着科学技术的进步，特别是电子计 算机技术的发展，图论的理论获得了更进 一步的发展，应用更加广泛。如果将复杂 的工程系统和管理问题用图的理论加以描 述，可以解决许多工程项目和管理决策的 最优问题。因此，图论越来越受到工程技 术人员和经营管理人员的重视。 关于图的第一篇论文是瑞士数学家欧拉 （E. Euler）在1736年发表的解决“哥尼
斯堡”七桥难题的论文；德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，（见图8.1a）当地的居民热裹于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图8.1b所示图形的一笔画问题
斯堡” 七桥难题的论文； 德国的哥尼斯堡城有一条普雷格尔河， 河中有两个岛屿，河的两岸和岛屿之间有七 座桥相互连接，（见图8.1 a）当地的居民热 衷于这样一个问题，一个漫步者如何能够走 过这七座桥，并且每座桥只能走过一次，最 终回到原出发地。尽管试验者很多，但是都 没有成功。为了寻找答案，1736年欧拉将这 个问题抽象成图8.1b所示图形的一笔画问题
哥尼斯堡七桥问题二D图 8.1a
哥尼斯堡七桥问题 图 8.1 a A B C D