数学建模之图论

杨利霞

数学建模之图论概览

问题引入与分析
图论的基本概念
! I( ~5 \" g9 _8 \最短路问题及算法
最小生成树及算法
7 }& z; F% @+ {旅行售货员问题
9 ~- \' {6 [6 z  W8 W- [6 ]1 {模型建立与求解
1.        问题引入与分析
+ D/ h- s' \8 }3 ?" @
$ l4 G1 N7 q" v7 e+ x4 d9 U1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

- `% [% S$ c# `" N; s* ]. |今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
3 _! d0 R2 V( k5 b, ka. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
. t5 W( I7 d9 K/ |9 t0 {: W7 L3 Ub. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
( g# n3 C( D+ k

公路边的数字为该路段的公里。
$ d* M0 |* X( M9 N0 j
* a; s/ M8 e2 T2 [& v2) 问题分析：
0 `% w, M1 a) }0 t8 l# X
* e4 t8 J' a+ K# S) o! f8 ]. }+ z- U本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
0 i* A- D3 J( v9 T) }将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.

本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
# o, [7 v0 d3 P- A* t' s7 Q如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
( [# `4 a- q" Z众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
9 h- {. m$ [& {显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.
! L7 q# r* j& t/ s
/ j3 Y7 C! t* ~; j2.        图论的基本概念
( e! d' R* d+ M+ Y* U; w
  {0 X7 J8 l0 T' N3 K图的概念
, E9 b2 {5 y- k6 M- d赋权图与子图
图的矩阵表示
' b8 g; t+ n( [4 Z1 }& M图的顶点度
& R+ o6 N  O! [% j# |路和连通
1) 图的概念
4 N, {" @( y1 g: F

, o5 n& V6 G- R2 q# a; Y7 c


( f3 X8 |2 L' z. Z) _. L4 Q) C* I' R
$ n1 G6 E+ r9 I6 g) Z4 A+ m- P
( l6 Z& k% @& c( F: e( }' E/ o
/ W4 g' [. P" A1 Y0 m* y$ d" d8 |
/ `0 S& p$ G# L" E5 `" X) l- i
& Z) R8 o1 w: \# Z8 X) ~
; m4 J% n3 w3 A* R4 Y




1 f: c8 b% `9 y6 V5 e$ w2 z




" K) ^1 X; X9 k2 ?: A' }
! H! K. e) z* a8 M

3 H0 c) H& E8 a' w" X


9 p& P( h* x) r  C& _5 a3 z2 ^

0 Z3 [' d9 Y' f' ~: c9 Y  b8 \
& O5 R2 X1 B& G. w1 O3. 最短路

2 T6 ]' v" {5 o$ ]. {! }# K5 X9 g( IDijkstra算法
: C: Q6 I) d( q6 Z7 @- t4 f
略

! v" j& Z$ P1 SFloyd算法
3 a; ?, M) N0 a' N  Y, _1 ~
' Y4 o1 s2 D5 k" F算法的基本思想
( b5 e$ a& Z. U( r: f; R* ]
3 ~7 j/ a8 R# z$ r( F直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
（III）查找最短路路径的方法.

# J$ ^/ c* h0 ]% y* J2 @Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
, p9 m7 c" i- w7 z1 F% a* Z" M: o

: O2 U2 t6 `6 H, U" N8 u& W
% G) I/ Q; S: e" k6 A/ Z
) c2 A- \9 P" n在这里相当于v1 v_1v
+ D5 [: o. r9 }$ K. {4 f1
; ?7 h& O. E, [9 a/ P1 F: Q​       
被打通了，此时v1 v_1v
/ q4 p2 ]; u" ]4 S% \* g8 D1
1 d6 R: [1 h8 b; o​       
: }( \8 [, w2 I% u- ? 就可以作为中介点连接。
' M) s2 @! ?+ Z# e% v1 s: k) f2 [于是遍历和v1 v_1v
- E% H0 A4 e4 v, _! u1
0 W/ z, Z( N# l​       
: Y- I" [$ G! b. k 连接的点，例如此时遍历到v2 v_2v
7 c5 g5 }8 N$ d4 M; |! I4 T4 n2
! x, Z4 u$ X) B0 h& x6 ^7 H. D​       
。
- V- I% O7 D' X6 w, T) W然后再以v2 v_2v
2
​       
1 S, q7 i) H* `# G% W8 C 为基准，遍历和v1 v_1v
% z: X1 s+ E* n4 q1
1 h: u( o8 u9 W  y9 `1 q  ]​       
; M$ p3 ^/ L, u) j# V# h( N 连接的点。
: @* ^! l7 e5 S+ v) ~: x所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
( u, T; H) }, s, Z2 v6 s4 x

0 z& l3 b- l( ^0 [: b
/ {9 o$ s4 x3 D5 t+ w1 g- h5 O
+ G+ b/ W5 H) ?" x
& {2 P) S+ g) M2 h& \

% z, ], ~6 d- p4 ]% c
( r, l' j  @' p, `. n8 d' O
; L% w0 }. T! K0 R5 g这里的逻辑是这样的:
8 V8 R. K1 r" }最小生成树
" Z  k( F, W0 i5 p8 X9 o& s) J
（略）
; O, k+ [7 I) D( Z; D6 J————————————————
' ^- g0 p5 k( y/ N' b) K1 x% r版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
: Z( P& G& V1 v  x- q! r3 Q; L

) ]# E1 `5 d  y' J4 F