数学建模之图论

杨利霞

: Z7 S4 w; D$ L# M; Y. J; J数学建模之图论概览
! }' j0 w; Q7 k# `( b! ]
问题引入与分析
. ?  Q0 v  x2 f: t图论的基本概念
' p3 ^* L! E! f% B( N2 L最短路问题及算法
最小生成树及算法
: F* }; H; m  h# S旅行售货员问题
模型建立与求解
1.        问题引入与分析

1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
+ G- {! }2 u& y- m) i6 Ca. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
+ V) e2 R2 X/ D" q1 Sb. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
6 G  `: j% ]3 s9 X8 }7 j
+ {/ [0 ?5 N2 @- `( A
% E( q6 F% `" r2 |; y公路边的数字为该路段的公里。

2) 问题分析：

* Q- d) l% w, w+ K本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
1 ]1 @0 z. l3 I4 `/ j再回到点O，使得总权（路程或时间）最小.
' C0 W! g4 U3 l& T' K
( F" ?4 o, w0 V$ Z1 v. k. ?本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
  b! N( T+ C% j" ]& k+ t+ R- V. a1 F显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

+ `; }& @6 G5 j2.        图论的基本概念
4 p1 f  R0 s+ x
图的概念
. \: U" G: ^+ ~- C赋权图与子图
7 n1 y3 e  J1 P0 l/ o% S& G3 X图的矩阵表示
图的顶点度
路和连通
( o: Y5 U* u% }7 }& o* g1) 图的概念

. I; n1 m# q) C0 t4 A  x
" X  M! _  J, X8 C* k+ l+ U
% d+ l; d; d* k  _/ i

3 j0 ?1 A5 ^% }; n3 s) j. h2 y
; k1 M* ^$ X+ S


, Y) O- m2 p# `' g2 w) K( U
! H" f' i; L5 j6 L4 h
5 |: q* j8 G9 Q  x; c( X

1 ?0 q+ I8 t1 n; O+ w

/ T6 l) F! Z8 K1 R5 u) r: U

4 n5 h8 Z3 y! W; B


3 V" Q: D0 `% R1 Z. f6 i
0 X4 J7 [0 Y5 ~- @


9 F+ a4 y% x  ?- B* E% l


/ h2 y( }6 w# G' B5 O2 ?


3. 最短路

Dijkstra算法
  h2 |4 f% U9 p$ w. X
略

Floyd算法
4 n2 D/ Q5 b" ~6 R
算法的基本思想
/ ?+ c& Z$ I( H/ D% c3 O' w
直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
9 U6 o& t) n) K0 w（I）求距离矩阵的方法.
) X! s5 ^3 I3 O/ C. z（II）求路径矩阵的方法.
, R$ @$ a  |0 Y1 ^3 J& R（III）查找最短路路径的方法.

Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
( T1 o" U! M# z1 k


1 i4 K" M# q9 K* A+ U" F, r5 a
' d: }! B, c+ g7 I; l4 ?在这里相当于v1 v_1v
1
​       
被打通了，此时v1 v_1v
( Y/ o6 v3 b1 R' d! k1
​       
4 q0 x' U  p# A 就可以作为中介点连接。
* @! {* J8 w* D于是遍历和v1 v_1v
  l% g. n; L* P2 z+ l. E1
​       
5 d1 ]/ t& P" m" |0 P& Q* T' I% U 连接的点，例如此时遍历到v2 v_2v
' X, |; t5 I0 j' }* x# w$ k2
​       
) s9 D7 u7 G: G: O: [: E 。
然后再以v2 v_2v
2
​       
& O+ H5 ?$ {( ?; L7 w% ^1 _5 M 为基准，遍历和v1 v_1v
/ g$ B/ L4 t1 d1 f1
​       
* A6 K  V) |$ Y7 t2 A1 T' L 连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
9 F' Y9 b) j8 S5 f- Z* u- I

0 j& S' {3 L: D% f
0 L* {  Y2 ~% u4 s) S5 ~8 C
& k8 E! A% q6 ^) j3 i

, }& L# H9 D" W) ]


" {6 ?' O5 \/ d$ i4 r这里的逻辑是这样的:
最小生成树
$ N: e0 Y7 ?6 Q7 N3 Q) Q# T, B
( A0 q+ ]' h* G( Z: |2 s（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
+ ^! i9 G" U4 l3 F8 [# |/ m原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
1 u/ b' u$ v3 b, e. I% D