第5 章 网络最优化问题课时：12 学时5.1 图的基本概念5.2 最短路问题5.3 最大流问题5.4 最小生成树问题5.5 旅行商问题5.6 最小费用流运输问题5.1 图的基本概念 例6.11734 年, 七桥问题( 德国哥尼斯堡)民间流传难题:一个人如何一次走遍七座桥且每座桥只走一次?1736 年数学家欧拉证明了鉴别准则: 一笔划问题( 欧拉定理) 例6.219 世纪, 四色问题四色问题的内容是“任何一张地图只用四种颜色就能使有共同边界的国家着上不同的颜色。”1852 年，英国搞地图着色工作的格思里，首先提出了四色问题。1872 年，英国数学家凯利正式向伦敦数学学会提出这个问题，于是四色猜想成了世界数学界关注的问题。 美国数学教授哈肯和阿佩尔于1976 年6 月, 使用伊利诺斯大学的电子计算机计算了1200 个小时，作了100 亿个判断，终于完成了四色定理的证明。 不过不少数学家认为应该有一种简捷明快的书面证明方法。其他例子.电路图、管道图等。20 世纪, 与优化问题结合起来.最短路问题、最大流问题、最小支撑树问题等等。1. 图(Groph): 点(vertex) 和连线的集合.不
