第十章 图论与网络优化 1图的基本概念 2最小树问题 3最短路问题 4网络最大流问题 5最小费用最大流问题一些问题 图论中著名问题. 1736年，图论的创始人Euler巧 妙地将此问题化为图的不重复一笔画问题，并证明 了该问题不存在肯定回答，发表了第一篇论文. 例：七桥问题 A B C D 问题：一个散步者能否走过七座桥，且每座桥只走 过一次，最后回到出发点。例：四色猜想 能否用四种颜色给地图染色，使相邻的国家有不 同的颜色。 点：国家； 边：两个国家有公共边界。 问题：能否用四种颜色给 平面图的点染色，使有公 共边的点有不同的颜色。 公元1852年，格里斯发现无论多么复杂的地图，只要用四种颜 色就能将相邻的区域区分开来，这就是所谓“四色猜想”。 直到公元1976年，才由美国数学家同时操作三台超大型汁算机 作了近200亿个逻辑判断，花费1200个机时，才取得了“四色猜 想”的证明。例：Hamilton图 游戏：用正十二面体上20个顶点表示20个城市， 要求参加游戏者沿着各边行走，走遍每一个城市且仅 走一次，最后回到出发城市。 公元1859年，哈密尔顿 (Hamilton)在给朋友格拉
