数学建模之图论

杨利霞

数学建模之图论概览

3 `" m+ ?2 y) i9 z! O5 y问题引入与分析
/ K. g2 s7 w. }图论的基本概念
最短路问题及算法
最小生成树及算法
8 O. F! o! c$ g1 I2 V0 ^旅行售货员问题
模型建立与求解
, z) }, I1 }2 J& z/ t1.        问题引入与分析

' Z! X2 }6 ~) `' w( V. ~" k) J1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：
4 `8 B( \: ~/ s
今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
! P0 Z0 b3 h0 b# O2 \3 ]a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
b. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.


' s6 D$ L6 [" ?公路边的数字为该路段的公里。
: z% ]* D2 [/ X2 V, V$ K0 j0 y) k
% O  L5 U( i, C( [1 c) O2) 问题分析：

本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
. c2 h1 O( I1 x! h& O( e将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.
; Z& ~  j2 Q; r
本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

2.        图论的基本概念
, c$ f5 g: W! X2 b9 M$ J
- |8 I1 b; w. k3 G7 B. r! ^图的概念
赋权图与子图
图的矩阵表示
图的顶点度
路和连通
1) 图的概念


, s5 N/ [( K* I
% [; d( e) j  g5 U* x
2 h1 H9 ]. d# k" B. Z+ Y
( v$ i* E$ Z9 p: g& ~
3 Z  g% z' L% X$ P) T: t
) X9 L3 l3 S. N2 i5 _

/ i; B, F2 N6 v# r( y7 \

/ i5 `2 j" [1 q" D. E
6 J/ l2 g* @$ D+ U( \( E1 ~3 F

' p" X  O2 k% M% c& C
( g0 p% ?7 L; ]2 ^. o$ q
. Y: p' ?3 t" V7 \6 X  A$ {



- R" W- m$ J/ y% `" H; |! U3 b( n' E
/ c% {4 U9 \0 w. w/ |/ v
' ?4 a* M" U' M! C+ T% ~
, c7 Q' t: k4 \; g" h






3. 最短路

0 z' n; P$ ?6 R' B- j% T1 o& P/ YDijkstra算法
2 Z8 t% ?6 ^0 `( {
略
/ f  m5 E- n* O5 i7 ?
3 x6 n& S# Z5 I. k5 a5 N- x( xFloyd算法

8 W6 o! v0 A0 q8 T' P算法的基本思想

9 a. @5 x+ ~1 ]7 E& \" J1 W直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
0 \0 \0 @  |0 Z- s（II）求路径矩阵的方法.
（III）查找最短路路径的方法.
2 s' o5 p$ F1 |
Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）

% K- i" O7 y% F7 R0 n) S8 u
1 _2 Q9 D' \- a! y. x

在这里相当于v1 v_1v
) q! ?$ J( D+ u, p2 d8 f% A1
​       
6 `* N' X" |. Z) } 被打通了，此时v1 v_1v
+ x2 m, A1 u5 S; [& x1
​       
就可以作为中介点连接。
于是遍历和v1 v_1v
1
​       
/ l; L% K- z# }5 I4 o# d 连接的点，例如此时遍历到v2 v_2v
2
) `8 q9 }( `' \​       
。
" l% W, S' U9 {& Z6 C8 D: f然后再以v2 v_2v
/ L/ G  S1 [% G3 W- q2 l2 B2
9 r6 e, }: T. j7 S1 R/ z6 b​       
为基准，遍历和v1 v_1v
; W" k% u2 L; R1
​       
, O; w" g2 k' C9 D( U& s1 E 连接的点。
9 D, |8 H1 z5 I1 L) |6 d( Q9 @: a所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。


- G4 Q/ C* |! m$ |



0 g$ S8 d" k/ K
8 A8 S. ^0 J  S: k0 V" X

) u% f9 ~- l: z# S2 c% W这里的逻辑是这样的:
最小生成树
$ ~% d6 d9 u" K8 O5 b
（略）
7 e/ }, }3 H' f. c; ?1 I) P————————————————
; U5 \2 [2 B9 ^2 T) k  T版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
7 v7 X# \+ s1 E8 ^; d$ I; `

1 G/ ~5 D; f  d; _5 k1 K! J