数学建模之图论

杨利霞

数学建模之图论概览

' h, R- L8 i% z! s4 `问题引入与分析
* d: f( g3 W( X" X6 o图论的基本概念
2 b7 q9 ?$ z3 d5 S, X0 B最短路问题及算法
' \  t+ ^! p6 N+ o- P! I2 M# S最小生成树及算法
0 F* U8 v7 N* h* {8 X* V! F旅行售货员问题
: l( U4 b' B2 T9 {; c! g- w模型建立与求解
1.        问题引入与分析
3 j9 ]( N2 x# }, N0 r9 F8 a- B
1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：
) @( ~, C3 w4 e% c
今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
: l8 t6 q. i$ h8 cb. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
0 f: g5 L3 D2 o& a
  U5 `( q' _8 n+ w% s/ o+ N- ?# a
公路边的数字为该路段的公里。
& g0 v8 `5 g  C: i
2) 问题分析：
8 a' G: R, p* D; C2 W/ p& D
本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.

4 m( I8 B2 f8 `# ~( [4 h本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
1 X8 V1 ~- s% `+ f+ i$ g) z显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.
. A! N& A  F1 L9 p0 q3 T2 }
2.        图论的基本概念
/ B9 s7 x! `0 m- q
图的概念
赋权图与子图
图的矩阵表示
图的顶点度
路和连通
" M$ @* S. }( o2 {4 D! B1 l) f' U1 I# Y1) 图的概念

$ |/ r/ `3 a6 A* A
  V+ y2 N( {( B  [( P6 h
! H& l! k2 h; h( g; k# f  K' ~: W0 o
  N, M* |& x% K% F! o( a% ~4 u


+ Z. m7 m5 ?1 ^& N1 @4 n9 e

8 L, i1 N* ^8 i




0 \% e0 L& l6 N, X  v9 U
* F" P# m% f- g, }$ Q" g, C  g

# `$ M: ]2 A" V: Q) ^& L
6 w1 p5 g3 `* e; [) a4 a
, E2 Q8 F! P+ N3 Y( o* t3 \1 b% g
0 B0 t& h6 ~  b


. |% V2 N4 j3 ^+ m0 Y
3 z7 b2 K) G3 a  K: i
( `- Z4 q# [5 q' v" ?+ E2 j4 C
6 C3 P8 y/ R: Z2 \' j
. [- E, h6 T: L


' K( |* o% L, m! h5 d3. 最短路

Dijkstra算法
8 Z8 N# H, M& s7 x' P1 B
9 ?" l0 w4 P7 q" s略

- z: Z5 y  M6 Z6 y7 Q, `Floyd算法
' n# G+ ?9 \! H1 R5 j# Y/ m
算法的基本思想

) Z5 v) g+ d( ^( I7 f直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
: a, p& N. o7 A- X（III）查找最短路路径的方法.

Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）

5 ^3 x; |! k- V9 R0 `) k  c

5 H- `, T1 Z" J; F7 g4 _+ G0 T2 G
; {4 z; }* @6 N7 z在这里相当于v1 v_1v
1
+ E; Y3 U5 K3 I1 h- r​       
2 E& K/ O- b' G 被打通了，此时v1 v_1v
1
​       
' P. }* M4 D; N' r7 W- e2 H 就可以作为中介点连接。
! Q% F3 y; X: y7 K- S* @& w5 i! d于是遍历和v1 v_1v
1
​       
连接的点，例如此时遍历到v2 v_2v
2
  @4 H  L. s$ x: j, m9 e( I​       
。
然后再以v2 v_2v
2
​       
  E7 g' Q, ~6 X, K4 c 为基准，遍历和v1 v_1v
1
* s0 A# e3 x$ x! H​       
7 _) W6 Y3 S, P1 d8 ?- K% a% e 连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。

2 V% s1 s$ g; c1 R7 `" [8 y2 r
8 E) e6 ^, L) l0 O

' |" {' D) h4 o0 X$ G
9 |  w% L1 w$ V5 j% k7 w, a


& J7 K7 j0 T/ z) D
这里的逻辑是这样的:
5 c, c# D( C; {7 z最小生成树

（略）
————————————————
4 e- W) L) X& ]% P1 o1 n! |, g版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182

* M. L  g- z' K* N