数学建模之图论

杨利霞

数学建模之图论概览

问题引入与分析
' {. B. \) B8 b图论的基本概念
. L' }% C5 E( a! Q: O3 a/ M) E最短路问题及算法
& C3 \+ K% q) @/ C最小生成树及算法
旅行售货员问题
模型建立与求解
1.        问题引入与分析
# P  {+ e% V- A" {& G  L5 ?! x3 L
; r" c2 M7 I3 e1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

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

7 c. n% ^7 c2 @5 Y+ v! H0 P. R
公路边的数字为该路段的公里。
. y/ @$ N  t1 F7 F" @
  X. f6 c1 i! i6 y; F2) 问题分析：
- x$ N' v. l/ m: w
" Z2 u( |& w6 H5 [) O( I/ H6 y本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
# z" T. Y+ K; `& R0 h: ^+ V( L( Y. k再回到点O，使得总权（路程或时间）最小.
& [& B3 E: S4 b# A) A
1 r7 v  G( Q* T1 g本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
6 x! x7 V( f5 Q% p4 K" g众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
& T9 T  @7 b+ Q# G' ]  `显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

( h2 l, Q9 h1 Q0 r- {  K2.        图论的基本概念
' ]0 W! w) R! t: Y% o/ c# _
( d- ^) E/ j1 A$ C图的概念
赋权图与子图
6 b) N; s1 S2 s/ _1 w( O图的矩阵表示
0 R# `4 `; K; P+ x( R1 {图的顶点度
路和连通
1) 图的概念

- k: z3 @! |( P2 F& h
8 T% s$ P+ G. [* P
1 t  [$ m1 ]: J* c2 R, ~( A/ B
4 U3 f6 b, Q+ b0 \
4 j# X) D2 c! f, p0 T9 i! }
) p# {0 A1 r$ p
* u! w3 r, ~6 t* k7 n% A

1 l  U+ ]9 j) g* ~2 ]' ^6 g! ?, G
9 }4 h+ s9 X8 z: @( \- A0 Z
3 m( y7 o4 e7 F' `  B+ \' I
+ K4 T, N( z- [/ z6 m

1 c0 s4 {2 W9 g' t. @



; P3 s  v, V" Q
5 p% H+ T( [2 S$ P9 J$ f


9 d1 P& V( M, v' B$ d

! t: b% g+ K; {6 o0 [4 Y% k
5 d0 j8 S% l2 _: D

1 V% ^' \1 F5 Q0 s5 }


7 Q$ g4 @8 p3 {+ i3. 最短路
5 ^- |% G  ~8 v
Dijkstra算法
, _( J8 K- G5 k$ T
  h: P- Y8 s+ v6 g略
4 _* Q! b' U9 e2 s* g2 h
7 K  R6 Y3 s* q6 a+ dFloyd算法
* }6 D  E  k' ^) q
4 i. w- R0 G- s- T算法的基本思想
9 X7 q# u5 ?" p2 V' d
9 j- S$ B9 }; o/ T+ V; g直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
  @# N. V% \: x3 K3 Y（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
7 c3 h) ]5 f4 U% f7 f- s' U0 |（III）查找最短路路径的方法.

) [8 P: O% W7 m, l' E: D* a  a- z/ |Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）

  b1 U6 v# w* N" T. M. c
2 z% W! Z$ z$ L, o7 ~' }, A. h2 x
6 m- {' D0 O/ K% P% o  i
在这里相当于v1 v_1v
* a6 K' q3 a- N3 X  J5 e1
​       
/ G+ I6 f; y  t( T0 V* y 被打通了，此时v1 v_1v
1
​       
1 h2 f0 Y& f4 _4 O6 g 就可以作为中介点连接。
; p, c$ Q$ D: A2 j- \于是遍历和v1 v_1v
1
. C" b0 k) I" H* J  c. Q​       
连接的点，例如此时遍历到v2 v_2v
2
​       
。
然后再以v2 v_2v
2
2 I. @7 }- c* ~; p$ m. ~% B​       
为基准，遍历和v1 v_1v
1
: `) I1 q0 l+ z9 Y. e) j8 a​       
连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
2 S. y4 S* J0 l$ c4 T
) W5 U6 [+ L# V/ r8 g


7 d: J1 C! L5 r# W

) w! F! I( ?7 _# X& u7 |% W5 q
$ F) K: I7 h' y$ S. ^7 Q- N
5 E! F& `9 d9 b% o9 I- w
这里的逻辑是这样的:
5 j6 }" g/ \; ]( b9 _- d最小生成树
( c* N% }1 T5 |: |& O2 V: _/ \
4 ]8 E1 [8 ?% X6 Z4 k（略）
————————————————
! ~$ Q7 D: B+ L版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
: Z# t* K* _8 i4 l; p" ?& B原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182

  B1 @( _4 M1 D2 _! q. p