04第四篇 图论方法建模2.pdf

20 第四章 图论方法建模 第四章 图论方法建模 图论是离散数学的重要分支，是研究离散问题的重要手段，已经建立起来了一些重 要的理论和算法，虽然这些理论还不系统、不完备，但是能解决许多的实际问题。不系 统就没有太强的连贯性，这就使得学习起来较为方便，可以随意挑选适宜的内容去学 习。 如果将要解决的实际问题归结为图论中的某些概念或某些算法，就可以利用图论中 已有的理论，这样就可以较快的解决问题。 在国内外的大学生数学建模竞赛中，利用图论知识去建立数学模型的机会还是很多 的。限于时间与篇幅，我们在本章先学习一些图论知识，愿意深入学习的可以参阅有关 的资料。然后学习一个较为完整的数学建模例子。 §4.1 有关的图论知识——图、算法与矩阵 一．图的定义 例１．城市之间的运输通路问题 A 城与 B 城间有通路，为２公里，B 城与 C 城间有通路，为１公里，C 城与 D 城间 有通路，为５公里，D 城与 F 城间有通路，为３公里，F 城与 A 城间有通路，为７公 里，B 城与 F 城间有通路，为６公里。问 A 城到 D 城的最短路程为多少？ 用这么长的一段话来表述，听起来太累，想起来也不清楚。若换一种方式，用下面 的图4.1 来描述该问题，看起来就清楚多了。 B C A F D 图4.1 由此我们引进图的定义。 G { (V ),G (E ),G } ψ 为一个图，其中 叫做顶点集合，Ｅ（Ｇ） 定义１：称 G V (G) ≠φ 第四章 图论方法建模 21 叫做边集合， ，而ψ 是关联函数，使Ｇ的每条边对应于Ｇ的无序顶 V( G) E( G) I φ G 点对。若 ，而 ，使得 e u v e E G∈( )u, v V( G) ∈ ψe ( )uv ，则称 与 、 相关联。顶点 G u v e u v 和 称为 的端点，此时也称 和 相邻。 一个图常常简记为 G= （Ｖ，E ）或 G （Ｖ，E ），这是因为边集 E 中的任一 元素总 是和某二顶点相连接的，所以 V 、E 确定了，就可以了。 上述例子的图即为：Ｇ（Ｖ，Ｅ），其中Ｖ＝｛A,B,C,D,F ｝，E= ｛e ,e ,e ,e ,e ,e ｝， 1 2 3 4 5 6 e =AB, e =BC, e =CD, e =DF, e =FA, e =BF 。 1 2 3 4 5 6 说明：①这里用图表述城市间的运输通路问题很清楚，说明对这类问题，用图来表述是 恰当的，“图”是一个强有力的表述工具。 ②数学里有“图论”这门学科，一个问题用图表达后，可用图论的知识、算法等来解决 此问题。关于图论方面的知识可参阅有关的书籍、资料。 ③若Ａ为一集合，其元素个数记为：｜Ａ｜。如上例中的顶点集合和边集的元素个数分 别为：｜Ｖ｜＝５，｜Ｅ｜＝６。 例２．哥尼斯堡（königsberg ）