数学建模之图论

杨利霞

, m" z4 J/ q' I5 }2 u数学建模之图论概览

" l, s" H) N. m/ `# B- `$ d5 D; \问题引入与分析
' C& o# A9 v4 I图论的基本概念
最短路问题及算法
最小生成树及算法
旅行售货员问题
模型建立与求解
6 Z1 P# J: A$ U2 F5 o) l1.        问题引入与分析

9 ~) a8 A* @8 ~' o1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

& v6 w3 r) Y6 K1 Z; U7 N今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
( t* p2 x6 R2 C/ g, f: Ea. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
/ _+ [* t# v* Gb. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.

- c4 r* C) R6 |; \& E
) ^8 N5 c$ V! W6 [( y+ e  r# u公路边的数字为该路段的公里。
3 K: C" S8 |) i4 b: v" e: {
2) 问题分析：
! f1 t1 v" E/ i( z. l5 }, f* b
本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
" }8 F3 ^; i: n+ [! W+ s1 y3 }6 T将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
$ e: J, z, ~7 x  h" @" C再回到点O，使得总权（路程或时间）最小.
' \0 P0 d) w& n  b3 L, d! D6 |  ~+ ^
本题是旅行售货员问题的延伸－多旅行售货员问题.
. @7 e  i, o( {0 Y7 Y0 {. _3 E本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
* P0 z. T# d+ Q, v' j如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
! z' Y5 S9 G7 C5 F众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
! O7 \2 n' ]! i# k, m显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

; D5 H/ h0 g1 n" A( _, J2.        图论的基本概念
& \7 C6 q4 c& I( \* s* I
0 g" T2 m5 A  M! W5 p: n* f图的概念
7 H% n* T, ]# X. q( z, p/ _1 r赋权图与子图
图的矩阵表示
图的顶点度
路和连通
. y. B4 p! V: b( R1) 图的概念
' A( e/ _, m7 R; {  L/ Y
8 ~. k' r  {! q/ r) o7 S0 B



' D- I" U. r% Y2 _

3 @4 I- h5 I4 T9 s6 V+ w$ e

" L+ [. F4 [* u7 A4 C


8 ?. U! a& T+ R" s9 x. w' y
3 X/ h8 s: ]) B& o1 a) y
1 f+ E1 ~* l2 B5 N, o& C
  \& W8 \6 j4 s8 V& X4 `3 y6 K# o! r




2 S; p9 O6 g- p/ t7 o
+ u0 k! w! Q2 P& x. A7 c: L
: B+ ], l" I3 p* q3 F0 Q5 n/ @8 k







% \1 m9 t8 P7 l1 C3 B, K& P3. 最短路

+ ]4 P/ s2 J5 sDijkstra算法
1 N. I; p" }- t% g' c3 A
略

Floyd算法
7 H/ O, I3 x! q# E( K, t
0 [) u% i& E, |/ ?# @. S算法的基本思想
: y) v( N# c( V. Y$ i
直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
" u" i' y- n  L! U4 n; i（I）求距离矩阵的方法.
9 j1 ~; b" B  J（II）求路径矩阵的方法.
（III）查找最短路路径的方法.

Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
9 F, A0 x8 m3 ^$ r
# @0 f- [' w% X: B8 N
1 C3 N% c, v# H! N2 Q* z
7 f4 i! q( I8 v
/ @3 q/ ?7 S" E' }' `! A9 @在这里相当于v1 v_1v
1
8 r/ N' F+ E9 T$ G+ V) |# |3 A  J9 M# h​       
被打通了，此时v1 v_1v
1
​       
; u0 t+ L  V1 d6 r5 h4 j- Z$ W 就可以作为中介点连接。
于是遍历和v1 v_1v
1
​       
连接的点，例如此时遍历到v2 v_2v
2
8 n8 u4 j1 N' v7 V) @- ^4 Z​       
, O" E% m  {" |' P 。
然后再以v2 v_2v
2
$ K2 J; |! `( u9 c% S8 U​       
* ^% o4 h, ~" P7 e$ P6 m+ [  K 为基准，遍历和v1 v_1v
  M/ d9 n" ?) [& u. B, h1
8 a# N9 B' ~/ L: P! U2 G# u​       
6 h8 z% j0 F) _( G# H9 M, Q8 ? 连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
: V7 x9 D) k7 y+ G: D9 m, V
* N6 o- Y. Y# F


! l1 i$ C% `& D! j




+ v# j* t3 M/ w/ o- {4 m/ s( b这里的逻辑是这样的:
最小生成树

/ V3 N  g* n' b& D* |, D' r! b9 F（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
, o9 M, U  O1 r$ i$ W3 e

6 H/ x& W* v* `$ t/ o1 `