图与网络优化决策的图论方法
点此进入淘宝搜索页搜索分類: 图书,自然科学,数学,代数 数论 组合理论,
作者： 刘桂真著
出 版 社： 上海科学技术出版社
出版时间： 2008-4-1字数： 80000版次： 1页数： 102印刷时间： 2008/04/01开本： 大32开印次： 1纸张： 胶版纸I S B N ： 9787532392407包装： 平装编辑推荐
本书是关于研究“优化决策的图论方法”的专著，书中主要阐述网络最优化问题中运用的一些重要的图论方法和用图论方法解决的实际问题，如最小连接问题、最优线路问题、工作分派问题、网络流问题，以及图的染色和标号在实际中的应用等。本书给出了简要而精彩的证明，使得读者能够体会到图论方法的精妙之处。
内容简介
本书主要阐述网络最优化问题中运用的一些重要的图论方法和用图论方法解决的实际问题，如最小连接问题、最优线路问题、工作分派问题、网络流问题，以及图的染色和标号在实际中的应用等。书中附有大量的例子说明图论在自然科学和社会科学中的应用。对于图论中的某些重要结论和著名定理，本书给出了简要而精彩的证明，使得读者能够体会到图论方法的精妙之处。同时，我们也提出一些没有解决的问题。
目录
前言
1．图论方法与问题
2．最小连接问题
3．最优路线问题
4．图的匹配问题
5．图的染色
6．有向图
7．网络流
8．图的标号问题
9．图论方法应用实例
参考文献
书摘插图
1．图论方法与问题
哥尼斯堡（Konigsberg）七桥问题 在哥尼斯堡城的普莱格尔（Pregel）河中有两个小岛。在河的两岸和小岛之间有七座桥，如图1—1所示。问题是能否从某地出发通过每一座桥恰好一次而回到出发地？很多人尝试过，都没有成功，但却没有人说明为什么不能成功。直到1736年欧拉用图论方法证明了这个问题是不可能的。他将该问题转化为图1—2中的图，问能否从一个顶点开始一笔画出这个图形而回到该顶点？由于这个图的顶点的度全为奇数，因此答案是否定的。在第3节将详细讨论有关这方面的问题。由于欧拉1736年在他的论文中解决了这个问题并得到了更一般性的结论，使他成为图论的创始人，他的论文被认为是图论方面的第一篇论文而闻名于世。
现实生活中的许多问题都可以用一个图来表示。例如，用顶点表示城市，若两个城市之间有一条铁路相连，则在两个顶点之间连一条边，于是一个交通网络就可以用一个图来表示。同样地，用顶点表示电话，用边表示两个电话之间的线路，则通讯网络就可以用一个图来表示；用顶点表示人，若两个人认识，则在对应的顶点之间连一条边，一个图就表示一个人际关系的网络。类似地，化学中的分子结构、物理学中的电网络、计算机的联网等问题都可以用一个图来表示。将优化与决策中的实际问题用一个图来表示，通过研究图的性质并设计优化的算法来解决这些问题，这就是优化的图论方法。
……
