数学建模之图论

杨利霞

数学建模之图论概览

1 P& \' m) U' c5 _. K0 p问题引入与分析
/ {( A1 L$ e% Q图论的基本概念
最短路问题及算法
; @5 ?# ]" C* Z最小生成树及算法
: u$ c1 Z% O  F  D- e5 z. L旅行售货员问题
$ D( p0 X* J" \. z8 {模型建立与求解
1.        问题引入与分析

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

$ Y. e  B8 M: _2 Q' `$ F6 @9 h/ {今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
b. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
0 n+ \8 Q, B. P9 m' V& n+ R
  U; W6 d& m( U- \0 L
公路边的数字为该路段的公里。
7 f0 U) c3 ?6 \2 f9 D, m% r" S
" ^9 h5 |, h% d0 |% [0 H: ^2 B9 E2) 问题分析：

, ^& g6 }% ?) P+ y* i/ ^3 O本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
5 f1 U' E' v+ V5 i" `* x将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
9 S: h8 G9 k1 o' x$ ?- I再回到点O，使得总权（路程或时间）最小.

7 ~% L: `- @1 a0 m$ l% I  S$ y本题是旅行售货员问题的延伸－多旅行售货员问题.
  h1 z2 Y6 N0 I0 [# ?0 r( V本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
+ ]+ t6 }! o3 J# \* t  P) ~如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
5 V1 s7 l2 I: X# m1 T5 T  u1 L! M显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

+ N% C2 o/ T& J& ?2.        图论的基本概念
% r' T6 m0 H8 f: h/ L9 o! E# u
图的概念
赋权图与子图
4 W" U, ^$ o' ?+ W- A图的矩阵表示
% R  Q7 x  k6 e1 W' i1 w图的顶点度
路和连通
/ B6 h1 `" R2 N8 b+ r1) 图的概念







) ]( J% a) l- [* m: K2 e



8 S6 f; H4 x# T* H) U; D( K. C9 X2 D3 f
* [6 R( P5 h# Q3 H/ }: g8 P- Y9 j
6 B+ f" J1 Q9 E




/ {; j( j' h% \; M* q
' x% l' K& j3 U7 Y7 p
$ B) |( {" i, N9 k0 z# ?
: V1 h8 R# R4 D

4 w, T8 n" d6 f; O: M, k% ?
; B$ J: |; X4 k8 [. ]) a


$ U3 u- v7 f  I+ D
* P  g" x  e4 e9 @

3. 最短路

- }7 y; c5 R& [" w' Y0 gDijkstra算法

略

; Q! {. y5 F  JFloyd算法

) h8 R% x! _5 ^' N% m算法的基本思想

直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
6 m1 h- X- H) h' E) x$ L  Z（II）求路径矩阵的方法.
（III）查找最短路路径的方法.

  M$ I& Y$ k# @3 Z) G+ N+ A+ |Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）


& M2 U8 F! \( I( T' N

4 A; Q* l  m/ ~0 g3 @' ~在这里相当于v1 v_1v
) {( i: v# }2 _8 o% p$ ^1
' [1 z' y* f7 L9 m/ {​       
被打通了，此时v1 v_1v
1
  m4 O7 a! R3 P2 i' u& q* N​       
" H# ], I8 I% n5 D, F 就可以作为中介点连接。
于是遍历和v1 v_1v
7 V/ F; Y5 C" }/ b; e5 S1
' z) `1 {. T/ q  ~​       
4 k) o4 }! l+ q: Z# S2 n- e 连接的点，例如此时遍历到v2 v_2v
2
4 `7 [5 ^# w1 @' }8 v1 v, }​       
。
然后再以v2 v_2v
2
​       
7 z9 e% ]6 @) O& N6 w 为基准，遍历和v1 v_1v
4 M9 e  {6 }; Z" Y) D+ W$ B1
, Y8 q  Z, H% Q* _5 S5 R1 k) @​       
' @* N1 y. B' ?8 H% G 连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
3 v! v! [( L' J, p3 E$ |

* H6 X# z3 ~, c' D( K' K2 c. c, V
5 {, U8 i+ ?* ^# o4 \
! _% [' ?, Y" W: \* G$ O
. o- h( \% a, Q( I6 v2 v
, ^0 Y4 v3 {* k
; }8 O6 S0 p4 `# d
6 B2 m% z1 }7 y0 G( }( R
3 q; U; }" s3 B6 c. b这里的逻辑是这样的:
最小生成树
- p  L7 i3 @" }4 q+ r/ D+ U
（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182

6 y. l( {( ~# E% g+ {+ [1 d
9 _2 `% B( ?5 r: i# q7 P