数学建模之图论

杨利霞

数学建模之图论概览
1 `; m. g4 ?$ J. ?. a4 X$ m
) z# z) ^& D+ c. }- i, R9 ]% M6 B, ~问题引入与分析
图论的基本概念
最短路问题及算法
最小生成树及算法
- Z2 `) e, g3 T! ?. N; ]旅行售货员问题
模型建立与求解
: ?  Q1 `' g6 d, l8 z1.        问题引入与分析
% a( H  W! y/ X- D
# p) t0 q# F+ g8 m! Z0 X2 S! T1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

% B) N* l; J/ C" B) ~今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
( N! A: Q4 R; ya. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
2 Y% f$ Q% G3 f5 K3 Nb. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
# P; `* p. L; a( j2 a' T4 y/ ~

公路边的数字为该路段的公里。
. X7 y7 h' X" U8 D/ `3 ^* y
/ c' k/ g2 H: M2 q- @2) 问题分析：

6 b) b0 e, r# |7 I本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
1 R! W$ v, _% P. ^7 M8 a将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.
1 {8 N: h2 r1 `, W* F& M* @+ h
4 K8 H- l) i% N9 K3 {本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
. E6 Z) Q6 k. L" P( |# P: ?$ S如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
7 j  k6 P0 i! y9 k3 M0 o众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
& W+ w- l1 o" u* f3 e显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.
/ h* K8 ^6 N4 U" r& O3 b
! S9 w# Z/ v/ \( G2.        图论的基本概念

" |! C8 Q; x" H: K' _5 T9 D& ^图的概念
赋权图与子图
9 H$ M7 P4 Y8 I: [) I8 p% \' J图的矩阵表示
图的顶点度
路和连通
1) 图的概念
% X9 {5 N& d; d7 h& H
6 x( p- ~4 n. l
# q$ `8 g& N3 @3 U
  K/ p6 Y3 x$ Z" S8 M1 g9 l
4 J" q; e( }+ q4 c& Z9 H% x% Z
: ~+ H. }, k' T( ]
* C' x" F" c, a5 M% N  U, Q- V
9 A: G* h. D. C, {* ^

5 S3 F3 N  m  z7 p$ H





0 Y1 B+ T8 Q8 Z4 ?1 Z* }
7 ^8 X8 b" B7 e


) T2 r3 g2 @- h; |! H
, c7 U( y5 [6 L: `! }


! x) B3 C& H1 ~- A






3. 最短路

Dijkstra算法

略

Floyd算法
( Z8 y; f+ g( {) ]- h
算法的基本思想
- n! _7 h6 j0 N
直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
6 n$ ~; Y- d; w  m4 f8 E& u（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
（III）查找最短路路径的方法.
1 x! ~9 E6 C$ d' v/ x
Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
( z5 t+ q6 p6 W9 s) U. K


/ m% S% c  n7 @5 v9 K% C2 a
在这里相当于v1 v_1v
1
: e/ S  G2 F; p​       
0 M% }/ t$ R+ q 被打通了，此时v1 v_1v
1
, H/ m. k9 w3 W: L4 Z: m/ B​       
" _5 U* R8 {9 e; C+ ~ 就可以作为中介点连接。
于是遍历和v1 v_1v
3 H8 q0 H5 E3 C1
​       
1 ~( w& ~* d' _  G5 ]( X 连接的点，例如此时遍历到v2 v_2v
0 Z0 ]& ~1 U9 i+ W+ b2
( u. k; |; v0 C7 g; V​       
3 q; {; T; [7 ?4 W 。
然后再以v2 v_2v
2
​       
为基准，遍历和v1 v_1v
1
4 ^; f# Q4 |/ h! p! ^" p! s​       
连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。

! P# i6 O0 a0 |1 ^: m
1 [  p5 B; |: V+ Y$ o
5 d) ?& p5 }- G/ b: b+ T5 M8 S

  V3 X& k& g8 w, h



这里的逻辑是这样的:
* U9 M; E  ^' d% N" m+ A最小生成树

（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
! a# k: m& c7 C! o原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182

( Z# n/ x$ f# I2 ]9 _2 n3 v
1 y/ R7 h; l* o7 M