数学建模之图论

杨利霞

- i' m4 F6 J; h& N( ~数学建模之图论概览
3 U6 q  N# I3 s0 d3 c2 @9 _
问题引入与分析
" |. c6 T# ]# P0 i) S' e图论的基本概念
最短路问题及算法
2 @5 h" o0 d; v, Y' o6 {最小生成树及算法
' j, i! ^* F' N+ P旅行售货员问题
" J: ]  b' a1 T! u模型建立与求解
3 u/ U% Y' I2 ~* U* n( R: M1.        问题引入与分析

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

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

2 Y# s2 _+ U& [+ ^5 w/ Y
公路边的数字为该路段的公里。
: k3 n& `& N4 ]6 l" X9 ~8 p
0 A" e2 G5 S( S5 p5 F; L& X2) 问题分析：

本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
2 B2 j! e. U: d9 Y将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
# x# H$ W: d& D" _9 G+ Q再回到点O，使得总权（路程或时间）最小.
3 N  U9 i. @/ S
本题是旅行售货员问题的延伸－多旅行售货员问题.
' b4 s0 f/ G" i" |本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
7 J1 [* J, u1 B8 ~, c, o7 V) ]如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
' m0 d( A6 i0 o( O显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

2.        图论的基本概念

7 h# z7 U# |2 {3 ^9 W0 W图的概念
7 i5 Y9 C5 P1 F# u( X赋权图与子图
图的矩阵表示
  B4 \+ w3 c6 Y, w$ c图的顶点度
% S& d  |1 z* o路和连通
1) 图的概念
# Z. o* s' D) e& s' N! ]5 g2 H' X

7 X6 t+ N% m. A; G# ^5 a% z# @

! K5 R, R5 {7 r9 m* r/ F8 @% Y' m
9 S8 `7 b# `  j: S3 O/ g! o+ W. @
& d2 \: I$ z' [


2 C+ ?- e8 I' X  P9 h( p
% R; ]% d( J; u" A. Z' g1 L- ?
' ^" P# d9 r5 Z" G0 @; C

9 R8 d/ R- E* h7 T

9 q6 ~0 a& C9 k
8 L! R" @( Z+ J4 U
' t* y; S; ?; X' Z& m
* J  ]: x! K) b



; _! E5 A8 t- w, {) O: |; x8 e4 ^
) g1 v0 x2 i" c3 H! ]8 a7 g$ |, ^


: V$ v1 |! a- n2 l# Z


7 v2 L" L) {) W) i* U
2 k3 f  o8 Y' A  e& W" u, s' F, o; C3. 最短路
- g* ~. G" Z) c: }$ `+ v
Dijkstra算法
$ |4 F2 G: a- N8 V' H8 w. \3 g
8 `4 _" G8 }+ s略
) j( Y  |/ e# ^! r: J& l( t/ Y
4 A$ A( y" l5 {$ {; {1 v" DFloyd算法
, d, U" e4 ?. ~
算法的基本思想

直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
: k  ^& D. {: F, @! s6 V5 @9 i6 ~（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
" P( g  Y) x1 s  A3 x  o0 y) d（III）查找最短路路径的方法.

Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
9 m0 [! r- ?8 B2 B4 g) ]& b# ?. [* x
1 W5 T, y/ k0 G/ C9 U( I
+ E" ]' w* H! h% K  f
. y/ S- I8 z: ?# b
2 j8 P9 _& h: H- \8 c; H在这里相当于v1 v_1v
1
$ k/ o2 E; g) s0 s0 ?# X​       
  c9 V- v5 X( H/ ? 被打通了，此时v1 v_1v
1
0 U2 ^# }. w* Q% W" b4 S" ?+ }​       
! T8 F7 o4 A0 p5 U0 {4 K& x 就可以作为中介点连接。
) h- t( j9 ]5 z& C6 q于是遍历和v1 v_1v
& z" p3 n1 a/ T1
8 ?5 s2 a& O5 \/ h$ H2 Z​       
连接的点，例如此时遍历到v2 v_2v
9 z5 r5 e/ T1 j" H; V: Y, Z, {2
8 r- P1 j0 E$ S: k$ b5 T​       
. f, N5 x1 o- |, g5 E, R. M 。
& i$ ]4 ~# {+ r/ J8 M( x% L然后再以v2 v_2v
4 [. ]5 ?. v, M) u' ^, ~9 {- S2
, R4 e% _: |6 V( A( {# x! H1 \​       
为基准，遍历和v1 v_1v
; h+ ^, a, Z* q' n8 k1
​       
( i2 A6 e7 d# Y0 z 连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
# }) P+ s: Q; Q5 j% G* k

4 g: ^% c9 B! N1 t/ H1 j) [5 z3 T
8 d/ `* i! x( L7 H0 c+ Z
. Q. k8 p* p0 I) b5 J
, I9 I6 h( x+ }, K; }6 H. t. ^1 ?- c4 F
2 V, J7 C7 ?. W
2 s3 e" l2 O5 X* G
9 |6 e- W4 W8 L' P8 K3 e
这里的逻辑是这样的:
& i; }: ?8 Z( K& u2 m最小生成树
5 G% w, }! k' r& T8 F
（略）
( H4 _/ R0 U  I( c& G/ n————————————————
8 e/ {3 u$ x; ~/ y4 s版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182

' u" }3 i! _1 r$ @: i
) W. b9 q0 F0 |) W1 y1 W