数学建模之图论

杨利霞

数学建模之图论概览
$ H# _' j2 {8 Y4 Z. O
问题引入与分析
/ [& e) X  i' g0 `" F, V6 o图论的基本概念
最短路问题及算法
最小生成树及算法
: c6 o+ Y# _1 [3 S0 R旅行售货员问题
, M$ ~' i; T9 i* O/ K模型建立与求解
$ o: E- j5 ^( q" ~3 x6 m# W0 |- h1.        问题引入与分析
+ \- D2 V2 b- `  ?2 Y
, p3 f! Y: F+ q; T2 u+ E1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：
# G3 s, L7 C) ]: K, Q4 j
今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
7 F' K. w2 u3 u; L( o( _" Xa. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
b. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.


8 V& f$ ?) W1 ?8 M% W公路边的数字为该路段的公里。
4 c  k4 `$ N0 E2 X) {
0 e/ T( d) ]* `- ?8 O1 |2) 问题分析：

  c: |2 x* m) G0 j" Q5 S本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
% D+ \( q1 N6 f) J, `' d5 ?将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.
9 C$ O& t" Y/ K9 A  h# D$ D& Y7 A4 N! f
本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
" z( D# p$ D0 P: G5 ?& _1 `众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
  C2 G5 f% S, K% k: l1 q显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.
4 a, u% ^* }- C+ f! V, A0 }6 U
2.        图论的基本概念
0 [+ c  r. }0 x" s$ V
8 }3 J1 M6 r* K图的概念
赋权图与子图
; X% R: i# g- x. Q; n' ~图的矩阵表示
: z2 C* Z/ T$ g& r0 \5 j' p图的顶点度
3 ^' ]) S  N7 Z% u! |路和连通
; A& b. m' f" J7 I; e, e1) 图的概念
7 J; l( U9 p" }$ Q" v' T

' g( p/ K0 i3 A# x- [1 ^  V* e- S

, B4 ^" L& W, S* _5 K2 B1 r) E" r
; \8 F# C; ]1 m" M


2 f! {4 c9 G& Z+ w9 a! r5 S
- F- A( X1 V- P- X* L8 g

2 {! z. s4 j" p& R5 [+ |1 v3 U4 W+ {




2 ^9 D( T3 Y7 o- p

1 x) ~/ u, k  h+ W% C. E# _: S
8 C; T" i/ G. b
1 s0 L% r  O0 O
  _! o- {7 w1 ^5 e8 c
. ?  l$ z. A/ W( u& C& N





" J) S( J' U: r; U

3. 最短路

0 u6 J& n9 R+ Y! g; Y% ]Dijkstra算法
5 Z: z8 N! H0 J4 O
略

Floyd算法

7 s3 G: F: Y+ J3 Q# Z算法的基本思想
0 ~, b+ y3 y7 Z; o; h$ i* {: ^
- e2 n) G7 p9 q' }9 P4 K- e直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
+ o7 U8 A( }( \7 _/ A0 \（I）求距离矩阵的方法.
9 k9 }" {; K( q( k- X: y0 ~（II）求路径矩阵的方法.
（III）查找最短路路径的方法.
. w0 W. c. T7 K, u$ g
Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
/ a# k- z, Z# E9 g

6 G  n2 v! L" ^  m9 K+ i6 C; q

- Q% w! h, f# \; x, q5 z在这里相当于v1 v_1v
1
​       
; T. Z5 h( F3 L5 [# [/ H" W% F 被打通了，此时v1 v_1v
1
% @+ ]1 g9 r) ^4 e/ \+ O4 i+ G​       
就可以作为中介点连接。
2 O: J1 V# d* n1 j3 z3 ~7 i( y于是遍历和v1 v_1v
+ `/ w* A$ O/ F" H' a7 g9 g" y1 `% ~/ V1
: f5 m. s: M1 T& w3 M( b6 b​       
+ ?/ W1 S: h4 g  z( s0 ~% n  E. n2 u 连接的点，例如此时遍历到v2 v_2v
( G5 ?) \% ?  E) A" k3 |+ v2
: p! P3 \5 v5 m' h4 z( f​       
5 r# r. g( g3 z8 b# h. ] 。
然后再以v2 v_2v
" g( b# ~. q- s$ G4 ~2
$ m! p8 g4 T0 X' g# u! z9 k​       
为基准，遍历和v1 v_1v
# k4 G8 o$ t. r' g! B8 ^/ X1
​       
' n+ N* |+ u% C, ^ 连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。

/ I* S* v5 h; b& R& {- Q

2 B7 l$ d0 }( g! v: C& w( ]2 I0 p
) i% ~& U/ E( B' t
7 ]! z3 x! s+ C2 _, x! E



这里的逻辑是这样的:
8 f+ [! }$ n4 |; ]) ~/ x最小生成树
* L" [8 {5 H7 g0 B  g* T
7 a) q8 x# i2 ?- Z) C2 m) h, R. K6 T- G（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
6 j+ ~6 M/ r: v7 R: ~原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
* b" Y5 t4 B) m2 m7 h8 ?
' H$ b; _5 ~0 D$ _& M