数学建模之图论

杨利霞

/ Q7 v  Z5 E* g3 Q9 Z数学建模之图论概览
0 a8 `5 p& ]6 ?5 v
问题引入与分析
: t5 O, ^# E9 G0 J# c# t图论的基本概念
; _% A+ g5 t7 M) M# Y最短路问题及算法
最小生成树及算法
6 e" z! M4 e1 u$ @; g/ @3 \旅行售货员问题
模型建立与求解
1.        问题引入与分析

1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

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


* @+ i- C2 \! z/ `' C. g) W公路边的数字为该路段的公里。

$ _( E* P4 y% f" D$ l2) 问题分析：

本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
( o6 s! l4 V! I9 }# X9 ]将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.
/ O/ [' c, |- m9 v( @. ^- j
3 n6 ^8 B/ K' Z- V& C本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
& G0 L( z% i: @/ s+ _  _0 {如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
/ S: V) J* V5 ]  T* P+ C0 a2 D众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
1 t2 ^4 C  {/ a6 Z( N! h8 X/ O3 A: |显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

, y% \: z( @: y2 L2.        图论的基本概念

图的概念
赋权图与子图
) O: i9 e8 ]: z图的矩阵表示
% A5 p2 F7 h8 F( l+ F图的顶点度
+ M6 o6 h) o% s" b, h* \0 M' t9 I路和连通
1) 图的概念
) Y& s, l- C2 x3 ]6 }



% B- n$ A6 t% R% B4 a- h
3 x4 v4 d7 ~& W9 A+ Y, z

  J- f7 V5 A; X7 j; N4 p+ J

6 l( C7 D: O- _& v2 L# ]% N

- N' M5 z; a/ p/ R$ p9 C! }
; h' i, x# v$ r8 W9 i




+ l  K, D" P- M: Y% U

" ]% L# z+ o: S' K- H1 S
* x* l' X" g# X# i

" V; o- c- [, h( m. E

8 M5 s1 f8 v" ]; \- [

6 x" y% c; i3 {$ S



) {; o# C7 P- b# u2 H% A) l3. 最短路

Dijkstra算法
& j* m4 s6 j1 L; m. i
略

Floyd算法

( L# a" |8 T+ u2 `8 e! b' u9 {算法的基本思想

直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
8 F7 E! O6 e% |$ ]& q% `/ f（II）求路径矩阵的方法.
; T2 n& A' j# m3 y! Z（III）查找最短路路径的方法.
7 ?- C7 N8 I1 b3 C2 B; L
Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）


/ V; E8 H( @9 f6 j' ^) |
; X8 C/ z% W7 e0 f* Q4 h5 W* K$ y, e
. M6 i! D# |  E. D  X在这里相当于v1 v_1v
8 t* G8 r3 {5 d3 d7 D& I1
​       
! j! Y0 q! ^; k7 c& e 被打通了，此时v1 v_1v
; d. N& h5 I+ b$ o6 G1
​       
就可以作为中介点连接。
3 i6 J3 c' ]3 L3 L5 w+ W6 W0 M- y, _于是遍历和v1 v_1v
1
​       
8 H$ i) @- _! ?; s 连接的点，例如此时遍历到v2 v_2v
2
: {& S* G0 P* [, ~- @! C! l1 `​       
。
9 ?7 @$ b; U- {5 s8 Q然后再以v2 v_2v
2
' u5 E- `/ p1 s​       
为基准，遍历和v1 v_1v
1
3 F5 \# m. L+ k# c% ?​       
连接的点。
5 H5 |2 T' N1 ]2 W4 R3 T所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。





1 z* G0 M0 c% p  U( O



这里的逻辑是这样的:
) g  z: g- u6 A2 m2 ^4 F7 j最小生成树
; i+ _$ j3 D, {1 t" W
（略）
————————————————
0 i* ^. p8 U* I& [0 K- L2 a/ P版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
. Q: s1 w* r' u9 J5 g& c* |! m
0 Z. H8 n& [1 H! ?
% s  _' \, E2 n: }# l* k