Page 200 - 数学建模算法与应用

Mathematical Modeling Algorithms and Applications
数学建模算法与应用

虽然能通过实验来尝试解决问题，但城市居民的各种努力都未能找到解决方
案。为了解决这一难题，欧拉采用了一种创新的数学建模方法。他将每片陆地简

化为一个节点，而每座桥梁则被表示为连接两个相关节点的边，由此构建了一个
包含 4 个节点和 7 条边的图形模型。问题转化为了能否从任意一个节点出发，连
续经过所有七条边后返回原点。欧拉深入分析了一般性一笔画问题的结构特征，
并提出了一个关键的判定准则：即图形必须是连通的，同时所有节点都要与偶数

个边相连。利用这一准则评估七桥问题，欧拉得出了“无法完成”的结论。这不
仅圆满解答了 7 桥之谜，还标志着图论学科的诞生。
我们首先通过一些例子来了解网络优化问题。

例 最短路问题
一位货车驾驶员被指派任务，要求尽快将一批货物从 A 点运送至 B 点。鉴
于 A 点与 B 点之间存在着复杂的公路网络，提供了多条可能的行驶路径，这位
驾驶员应当如何选择最佳路线？如果假定货车在整个行程中的行驶速度保持不

变，那么此问题实际上转化为寻找从 A 点到 B 点之间的最短路径。。
例 中国邮递员问题（CPP － chinese postman problem）
一位快递员承担着向特定区域派送信件的任务。为了提高效率，需要规划一

条最优路径，确保从配送中心出发，覆盖该区域内所有街道至少一次，并最终回
到起点。这个问题最早由我国学者管梅谷于 1960 年提出，因此在国际上被命名
为“中国邮递员问题”。

第二节 基本概念与性质

一、无向图

一个无向图 G 是由一个非空有限集合 V(G) 和 V(G) 中某些元素的无序对集
合 E(G) 构成的二元组，记为 G =(V(G)，E(G)) 。其中 V(G) ={v 1 ，v 2 ，…L，vn}
称为图 G 的顶点集或节点集， V(G) 中的每一个元素 vi(i=1，2，…L，n) 称为该

图的一个顶点或节点；E(G) ={e1，e2 ，…，e m } 称为图 G 的边集，E(G) 中的每
一个元素 ek ( 即 V(G) 中某两个元素 vi ，v j 的无序对 ) 记为 ek = (vi ，vj) 或 ek =
vi v j = vjvi(k=1，2，…，m) 被称为该图的一条从 vi 到 vj 的边。

190