数学建模之图论

杨利霞

数学建模之图论概览
( Z" @5 R" j, n$ r. _% F
( D$ m# H3 X7 ~) G% v问题引入与分析
0 w/ `2 r: y8 V  f5 v7 H, O图论的基本概念
最短路问题及算法
; L5 h4 L3 }% e  @( ^. M3 G5 T最小生成树及算法
旅行售货员问题
# X- M; E9 p/ o. Q模型建立与求解
1.        问题引入与分析
3 I4 y* r1 J  u& |( k. K
/ O9 V. \6 M4 _& `3 Q1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

2 ?1 z9 U& Y. _2 U今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
# r) g. {  q6 v) T. b5 Ba. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
b. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
) ~+ z% U8 V. F! S3 n+ b( w

公路边的数字为该路段的公里。
- t- i8 W7 m8 z5 v/ F9 a
4 B5 K9 [% u2 p( s  @5 n; Z$ z2) 问题分析：

本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
* w& S6 l! K9 D/ U- Z7 T2 r再回到点O，使得总权（路程或时间）最小.

本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
) X5 A: q0 N  S& R如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.
7 @2 O3 a0 @2 R8 E8 |; v8 P1 H* A
2.        图论的基本概念
& o3 |( s/ q7 m9 `( L* b
2 B9 L/ C3 [$ |: y2 S图的概念
赋权图与子图
图的矩阵表示
图的顶点度
路和连通
0 t6 Q0 a8 E/ R/ k" U1) 图的概念

7 x5 l6 W% G, \! _
# M" F! r+ u0 E; e5 V
' v( P! \1 X+ m$ \
' N( z: |' B# n6 F- ^9 i; L
8 n4 D% p" L+ ~

3 I2 b4 W4 E, ?% Y+ _

& e+ i9 q2 u$ ]5 v7 y
& j! x$ b3 ?( E3 ]$ b0 _
' O) R7 s* o: i. s* b# r
9 Q' p$ D" m, T8 ]" `" Y7 |3 Q
9 R& V; T' h  E- ~5 z5 O
+ `3 m/ v! [  h0 q
& X1 C, X& ?' Q! G$ ^- ?& G: y/ R
0 m4 n) ~" M5 J' d+ L  A% A: x



+ {) c. q9 o+ T: f1 V
# U  k$ `$ t! @+ C, K) f0 O  Q
; o& q0 u) s/ a% |

* h' o" ]+ o. C  g( [0 @
" {, R% f9 a4 r4 q9 I2 p


" ?- b6 }, p  |2 L/ ]: T" [( L
1 E* ?; Z* e3 A0 V6 r' n8 I0 b
3. 最短路
4 Z$ h2 B8 v( P0 @
Dijkstra算法
# h& L5 Q+ \' k- u) ?
略
5 Y9 @1 K0 n# Q
Floyd算法
" U+ ?/ d, ^2 S$ P* U7 b& r, U( C8 q
算法的基本思想

直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
9 t9 ]+ n: g# z" P  _（II）求路径矩阵的方法.
; W% @6 u3 Z$ d（III）查找最短路路径的方法.

Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
0 u. F. l2 I7 x8 \- D


" }5 X! {9 u! Y4 R, N* A1 _8 u
在这里相当于v1 v_1v
- C) A3 P7 f2 r% ~/ a, a1
​       
( J1 o+ X, u! ` 被打通了，此时v1 v_1v
( R) p8 S3 u. U# t9 P3 m( {8 S5 {* ]9 r1
​       
就可以作为中介点连接。
于是遍历和v1 v_1v
' q9 o0 k3 v. O1
​       
连接的点，例如此时遍历到v2 v_2v
( U) t$ ~/ Q3 U  H9 \5 \2
​       
。
, o) j9 |" g( T然后再以v2 v_2v
2
2 w) F# A# m8 }( ~  f( C) M" r2 a​       
为基准，遍历和v1 v_1v
. \- U, d+ Y. U' S/ S- F. l1 z1 h1
+ _0 C+ L0 p1 w0 ]$ N5 e- Y​       
9 i  ]0 W& N' O; T' }0 Y# Z 连接的点。
% \3 J: m4 v( U6 X9 r% B所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
: K$ r6 x  ~6 q8 P# k" D% k0 a
6 z/ w  z0 m8 ]7 ~: q, O
: h4 [5 O; L$ E" P. J
8 s! N2 r4 z: p

1 g1 o( O( x, r, A# T$ L& |


2 T: X+ \. `. E, b, e1 Q* ^
) w  G5 w, l3 C4 \$ `2 `这里的逻辑是这样的:
最小生成树

（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
4 b- V# \6 I, Z' Q4 B原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
* S; \1 D" L5 x/ Y  S8 s