数学建模之图论

杨利霞

数学建模之图论概览
! U, J* p: M3 |8 a; |7 W- z4 U4 q
问题引入与分析
图论的基本概念
最短路问题及算法
最小生成树及算法
  a- t7 J7 V, o: Q* U( ^旅行售货员问题
模型建立与求解
1.        问题引入与分析
. W1 T# G! r: a
) D" U, C# ?& k+ E0 f1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

; c  V6 N" B- |# C+ V7 l今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
# C  D7 }' E( Wa. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
b. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
! ?, U8 |9 _3 Z: }9 ~
# }. x, w2 T. K6 U
公路边的数字为该路段的公里。
9 a/ N( L/ c- {* x# R. K5 o( L
) j! p+ n" V4 L# d# _2) 问题分析：
' e2 j( n0 c$ A, E8 i
, h5 G6 F! t5 m' ^8 {2 J0 I& X. v本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
' z9 X; \6 M& j" x! H5 c$ |; y7 p9 n将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
* I. ?* F  m$ N- d' [: J; k, y再回到点O，使得总权（路程或时间）最小.

本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
2 m' o4 F9 I% x! V, r% j4 K如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

0 t0 H+ C4 u! h) j- x) q2 k; {; b" p  c2.        图论的基本概念

+ }3 k( W+ P4 d* K- W1 B. e图的概念
赋权图与子图
- d2 G. y# f& S* g9 l图的矩阵表示
- a7 u8 f, x. _* `. G( n7 s图的顶点度
. ~  h- U4 {; I) }8 A1 F. b; v! H! w路和连通
: M3 R/ H1 w) Z5 u1) 图的概念
- P+ C# p% ?: g
6 |) r1 D: E' v. Y' v& o

: M1 N* n9 V1 z! d

4 e* t8 [* ~! C# K8 x6 g
' s3 G, p& H6 C# ?/ j! ?7 Z
4 Z6 ?/ \# M+ a& y
; h/ H) ~- s: a; @; K8 ?

: o) _, w7 E/ O
, Q) N/ j4 K* `  e& C: a  E
* i5 x, ^+ v! M; H0 S


( ^8 ?. I; e; Z  U/ E+ Q
8 O+ `8 p+ @3 F: ?$ x$ E: F) ~/ i

+ I: g0 T# z, [# r' A$ z9 B


9 J) t. J5 f' O% Q9 s* Y# z0 G



& O3 f0 B$ C2 p4 w



8 ]0 A) ~0 C9 _4 {0 N% {- Z& L4 y
3. 最短路
  L6 N+ N$ f8 E" Z# I
Dijkstra算法
* p0 d) g2 n" ]# G( X: l
略
0 d4 @" ~6 ^' E3 [
$ `( B4 X( ?1 G2 l( u3 `9 L* qFloyd算法

算法的基本思想

直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
: Y" M5 A: C4 h$ H7 l. J8 x（II）求路径矩阵的方法.
（III）查找最短路路径的方法.
. S2 w0 ~1 @; p0 Q( T- ^3 n
* ]' x$ ^9 D. b( BFloyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）




在这里相当于v1 v_1v
1
7 ~0 j6 v4 Z" k- p$ t​       
3 T2 I& @$ |( [- G5 {6 e; z4 Q) T 被打通了，此时v1 v_1v
1
​       
就可以作为中介点连接。
) H! v( Y6 T" T于是遍历和v1 v_1v
* T" B+ O8 ^- n1
​       
* q+ W6 l9 `# V* A. l 连接的点，例如此时遍历到v2 v_2v
2
% [/ ?. Y% K/ l- n8 Q6 q4 @$ d​       
。
; ~) g& j; D8 [$ v0 Y然后再以v2 v_2v
% V3 [( A4 u$ U' o; b2
( U6 H: F+ {3 L: Y1 x​       
为基准，遍历和v1 v_1v
) V4 m& {# e$ m- X' I1
​       
' n! }& f* {! E. ~0 w* F) ] 连接的点。
% y. X! o$ b6 V9 B$ X1 O2 P* X$ G所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。

: C" u7 R7 T, U: ?

6 r1 }6 B6 Z& K3 J% Z
) W9 v9 ~% D0 ^4 X! L; O
, s7 {! V0 ^" D$ M" H7 F7 Y( R! W



  {; H! {% q9 W! }( n1 d: U! A- h这里的逻辑是这样的:
最小生成树
( {" F" \: v4 K# T* M' i
（略）
) T2 \+ f! l+ \————————————————
/ O5 j; F2 z' S版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
. v2 k$ t( j5 H原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
) A! i' x9 ]7 E; s" H1 j: @/ R