数学建模之图论

杨利霞

2 h5 Q/ F1 N$ B* R+ O: V数学建模之图论概览
4 c9 u" h! Y: Z+ G0 }
9 S# H1 x8 s- c& v# f( [6 g* j问题引入与分析
/ n, ~$ K- z: V  o图论的基本概念
) G# {5 }) G3 U. ~最短路问题及算法
) o2 }6 E" }; Q7 k9 A5 K7 B2 f5 n最小生成树及算法
- k1 X! f4 c4 k3 N旅行售货员问题
模型建立与求解
1.        问题引入与分析
8 \' X. i6 J1 K( i5 C3 A# w1 `
. R: z3 L  m4 L) Y" T1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
( Z4 n2 l7 x; R" e3 C  [a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
; F# T3 g) ~; l5 vb. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.


: B  \4 q0 v. P% O( U公路边的数字为该路段的公里。
0 k* E( M! b6 ]1 k  c0 b$ {
2) 问题分析：
8 W1 ]( D' p" F1 E) ~
* P8 m4 f" h3 A- ~, k* ?6 J本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
( h. M) J  q6 Z, ]. x: J将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.
- m8 [+ R+ Y: Y! x9 W+ ]
本题是旅行售货员问题的延伸－多旅行售货员问题.
1 r- M7 P$ }  z% i; }本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
+ |: `, l9 u9 }1 F/ U& P如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
, x0 `, c6 x3 L9 Q* ^- [! x% ^9 w+ ^众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
- `& S0 _  g4 l2 P显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.
" P! D& y9 e; O2 U6 G
2.        图论的基本概念
0 v6 u  v3 f. f, c0 J& [
& }; N4 J- f: o$ @' R图的概念
赋权图与子图
图的矩阵表示
, k% }) n  @/ w4 f0 ~图的顶点度
路和连通
- _- u) n5 U! k  [* x+ P1) 图的概念
8 ^$ G' Z# M* K* U* |0 R


9 u) }/ }' {- N% h; F

+ j4 z7 F2 J: j, A( _: P9 D, a


2 L1 o5 ^- V" M! ]: G

8 T/ t4 [) Q# a6 {* ]% `
  {8 w5 |7 r; ~

' B# Z6 O/ G1 O
$ F$ K8 E7 j( B' Q7 Z& c
: P- V- ~# r  K' T+ _) a6 f



* A' d# m2 H  H% C( z# c3 @
% f* p, ]$ |( M" ]
- O: t5 R' c  x- m
* A# `7 r* a7 P2 i
/ j! d) \7 Z% O7 }; S7 B. T
6 F% J) C" T; ^# O

9 A+ y. F1 ?, D: D: q


- S9 ^: r0 `9 J8 m
3. 最短路
8 R/ ~7 E1 O) o  N  r5 ^3 j
Dijkstra算法
/ u: b. X" @- E
, s! o! T! ?& n/ b4 S0 W略
& V' u7 A0 p+ l; e0 [
7 I1 _& w1 m: Y8 z! l5 m* cFloyd算法
% v2 V% e( B8 {& x
算法的基本思想
9 ?" O3 S* _- a+ N4 X; m6 D6 ?
; @/ k0 g5 d; L9 q9 U) k直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
) |2 S  l1 \' ?5 W（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
（III）查找最短路路径的方法.
. C2 \7 K  g1 X6 [" B* D
; s/ m5 r3 a, W$ B; _4 }$ }. nFloyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
6 k6 F$ \( d& N4 a


  h8 I' _) l9 `! N% j3 c$ @
* }/ V% I( z' Q$ p在这里相当于v1 v_1v
( q# s4 W1 f# m! F! j) B9 p; F* o2 V7 O# l1
: B; r% e  s: I& H& c​       
- C( E' c! h3 y7 d- L7 Q  ]2 c 被打通了，此时v1 v_1v
1
​       
# b5 @7 H, E5 w& G% v 就可以作为中介点连接。
* b2 T7 F0 J- j: S于是遍历和v1 v_1v
& P5 e6 a4 D/ |1
! K9 x; G: I2 Z3 B, z, w​       
+ y* G4 n' l/ W3 A% z 连接的点，例如此时遍历到v2 v_2v
6 t* _' ~& M( n( K7 b2
' l% L2 k8 t( e) Q) f) |​       
( g7 C8 E5 ?5 a/ M% r. Q 。
然后再以v2 v_2v
2
​       
为基准，遍历和v1 v_1v
1
​       
连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
% }1 {( G+ L+ P: u2 s2 Z5 R$ L1 A% {



) j+ f2 P' P5 m* I2 _  \( a




/ M: g, m# w( P' l# U这里的逻辑是这样的:
* c  \6 l5 X% x3 O最小生成树

0 Z0 H/ w# p- O6 a' @（略）
! s2 \; z. W/ X! Z" M3 V2 [7 M* C& g* U————————————————
& f9 E4 \5 i' L: k* M0 F版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182

6 V' ?: ]5 }- s9 [# H0 f9 \
4 h5 }# q7 m* v+ c4 r