2009-7-26 1
运 筹 学 Operations Research
§ 6.0 图论绪言山东运筹,两论起家,一为规划论,一为图论,
—— 管梅谷（ Kuan Mei Ko）
图论的起源：哥尼斯堡（ Konigsberg） 七桥问题
18世纪 30年代，流经东普鲁士小城哥尼斯堡的 Pregel河中有两个小岛，小岛与两岸有七座桥相连,当地居民热衷于讨论如下问题：一个散步者能否从某处出发，依次走过每座桥恰好一次，再回到原出发处？
2009-7-26 2
运 筹 学 Operations Research
1736年，瑞士数学家欧拉（ Leonhard Euler,1707-1783）
研究了此问题并将其归结为一个,一笔画,问题：
为此，欧拉曾撰文,Solutio Problematis ad
geometrian Situs Pertinentis》（ 依据几何位置的解题方法）,是为历史上的第一篇图论论文,欧拉因之而成为图论的创始人,
2009-7-26 3
运 筹 学 Operations Research
主要内容：
0.基本概念
1.树 （ tree）,森林 （ forest）
2 CPP和 TSP
3.染色 （ coloring）
4.平面图 （ planar graph）
5.匹配 （ matching）
6.网络流 （ network flow） 问题：最短路问题,最大流问题
7.其它 （ otherwise）
2009-7-26 4
运 筹 学 Operations Research
§ 6.0 over