引 言 探讨从图中任一点出发，是否能一笔画出图 8-2(即一笔画问题)，欧拉发表了第一篇关于图的 论文，证明了七桥问题不能实施一笔画，结束了 当时人们的争论。从而欧拉被公认为图论的奠基 人。 1852年F.格思里提出了著名的四色猜想问题 幅地图只要用四种不同颜色着色，就可以使互 相接壤的国家由不同的颜色来区分。1890年有人 证明了五色定理。四色问题直到1976年才由美国 学者Appel,.Haken等用电子计算机完成证明。 8
8 引 言 探讨从图中任一点出发，是否能一笔画出图 8-2(即一笔画问题)，欧拉发表了第一篇关于图的 论文，证明了七桥问题不能实施一笔画，结束了 当时人们的争论。从而欧拉被公认为图论的奠基 人。 1852年F.格思里提出了著名的四色猜想问题， 一幅地图只要用四种不同颜色着色，就可以使互 相接壤的国家由不同的颜色来区分。1890年有人 证明了五色定理。四色问题直到1976年才由美国 学者Appel，Haken等用电子计算机完成证明
引 言 1859年汉密尔顿提出：十二面体中的20个角 分别表示20个城市，从某城市出发，访遍所有城 市，且仅访问一次，返回出发地的Hamilton回路 问题。1936年哥尼格发表了第一本图论专著，从 此图论成为一门独立的学科。 目前图论与计算机科学、 系统论、控制论等 学科密切结合，在工程技术、 生物化学、系统工 程、通讯科学等领域得到广泛的应用 9
9 引 言 1859年汉密尔顿提出：十二面体中的20个角 分别表示20个城市，从某城市出发，访遍所有城 市，且仅访问一次，返回出发地的Hamilton回路 问题。1936年哥尼格发表了第一本图论专著，从 此图论成为一门独立的学科。 目前图论与计算机科学、系统论、控制论等 学科密切结合，在工程技术、生物化学、系统工 程、通讯科学等领域得到广泛的应用
3引 言 图论的方法同样可以应用到经济管理、辅助 决策等领域，图论已经成为运筹学的一个重要组 成部分，它是建立和处理离散型数学模型的一个 重要工具。本章将先简单介绍一些图的基本概念， 然后讨论图论中有关网络分析的一些典型问题 最短路问题，最小树问题，最大流问题、最小费 用流问题和中国邮递员问题。 10
10 引 言 图论的方法同样可以应用到经济管理、辅助 决策等领域，图论已经成为运筹学的一个重要组 成部分，它是建立和处理离散型数学模型的一个 重要工具。本章将先简单介绍一些图的基本概念， 然后讨论图论中有关网络分析的一些典型问题： 最短路问题，最小树问题，最大流问题、最小费 用流问题和中国邮递员问题
第一节图的基本概念 图 在实际问题中，人们经常用“图”来表示所 研究的对象以及这些对象相互之间某种特定关系。 例如在图8-3中，我们用图表示了A,B,C, D,E五个城镇相对位置以及连接它们的公路网。 A E C 图8-3城镇公路网 11
11 第一节 图的基本概念 一、图 在实际问题中，人们经常用“图”来表示所 研 究的对象以及这些对象相互之间某种特定关系。 例如在图8-3中，我们用图表示了A，B，C， D，E五个城镇相对位置以及连接它们的公路网。 图8-3 城镇公路网
第一节图的基本概念 在图8-4中，表示了10个城市的铁路交通图。 北京 天津 济南 青岛 关郑州 徐州 连云港 武汉 南京 上海 图8-4铁路交通图 12
12 第一节 图的基本概念 在图8-4中，表示了10个城市的铁路交通图。 图8-4 铁路交通图