数学建模电子教案 v重庆邮电大学 v 数理学院 v 沈世云第三章 网络图论模型 一. 最短路(最短路径)问题 二. 行 遍 性 问 题v 图论（Graph Theory）是运筹学的一个重要分 支，它是建立和处理离散类数学模型的一个重要 工具。用图论的方法往往能帮助人们解决一些用 其它方法难于解决的问题。 v 图论的发展可以追溯到1736年欧拉所发表的一篇 关于解决 “哥尼斯堡七桥问题”的著名论文。 v 到目前为止，图论的模型和方法已被广泛地应用 于系统工程，通讯工程，计算机科学及经济学领 域，传统的物理、化学、生命科学也都越来越广 泛地使用了图论模型方法。由于这种数学模型和 方法直观形象，富有启发性和趣味性，因而深受 人们的青睐。从七桥问题说起 -关于图模型 v 哥尼斯堡七桥问题 v 七桥问题是发生在18世纪东普鲁土的哥尼斯堡的一个真实 故事。 v 在哥尼斯堡有条普莱格尔河,它有两条支流在城市中心汇 合后流入波罗的海。这条河将城市分割成四块:A、C两个 小岛和B、D两块陆地（如图）。为通行方便，在四块陆 地之间建了七座桥，每到节、假日或傍晚，都有许多居民 和大学生来此散步。久而久之,人
