数学建模之图论

杨利霞

数学建模之图论概览

/ H9 Y; @4 z/ C2 R- j8 ~问题引入与分析
图论的基本概念
+ i0 J/ E6 w8 W. g3 J0 v最短路问题及算法
最小生成树及算法
3 l: ]  P- \* x5 E4 @旅行售货员问题
2 v5 ]! |# D" s* O6 m. @模型建立与求解
/ F* I4 B8 h. M. X% _( I1.        问题引入与分析

4 H" A% {# |' t/ l) X# V1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
& k, o, N; d6 r  _a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
6 m( u( u1 d9 eb. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
, b( D  u0 {- m. K2 ~+ j2 Y7 b

公路边的数字为该路段的公里。
8 R6 s0 k+ Y7 d' P. ?
2) 问题分析：
2 R% a9 Q5 w) T! t8 Q& t6 {
本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
% h' r5 h: l$ Z! h6 _4 t将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.

本题是旅行售货员问题的延伸－多旅行售货员问题.
4 C! K  u' U5 F  u" a$ K( y# o; K本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
( ^: `) D8 U3 s* `/ Z4 Z众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
; i) ^1 l2 y1 j/ [9 s1 \  l+ i显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

2 I% r+ r7 G/ g7 a: O0 Y0 p( Y7 x2.        图论的基本概念

图的概念
赋权图与子图
图的矩阵表示
$ {) u8 H( O" K& e) F0 X图的顶点度
路和连通
1) 图的概念
+ q7 J( q3 I2 v( ^0 q

9 u( m8 D  E1 G; Y" `; w

- [2 D( z/ U- Y6 D- p
/ d2 A# [0 C8 V( j) d5 m



7 O1 n, W/ m  J8 n
$ G% M+ C- E) O4 B7 {1 z9 @


! G2 W+ }2 H3 j" Y5 z- V+ L
. r& Z2 x' `: v3 a) x8 n

) i9 X$ k8 Q( r9 s

' h4 n: D4 t  c  d1 z% o4 g# U

; G# S  _9 R) w8 z
; y( a/ Y7 ^& C( Q

* O+ z2 q8 T) g7 L# n4 o: Q
' D- G( H7 f; b0 G" }) p" s

9 p* B$ X  ^  b% x. |+ `
, t$ t! Z/ W( [- V( k& U

% _/ t( m: p' m9 i! H
& }6 N. }0 R0 H3. 最短路

9 j/ }. Y5 o4 P$ U7 U  U) |- q. @# YDijkstra算法

略

# k$ R( q4 \6 z& {# j) WFloyd算法

算法的基本思想

直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
& }9 k& b: {) X5 e' B+ V（I）求距离矩阵的方法.
! Y* d' @1 C% k- S' K! s  Q% S（II）求路径矩阵的方法.
# t3 T8 W9 Y- D- ?8 ~- A（III）查找最短路路径的方法.

+ f; X2 M: a. t8 |. _6 o$ a# kFloyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）

' z3 K. n+ I# D$ u2 B


' _% Y0 N, m1 H6 t2 |! }  m在这里相当于v1 v_1v
0 Q* B) i- y* H  Y; R; [& O3 N8 I; V/ x1
​       
2 _! w+ `2 ]1 R: Q: W# h7 x3 Z 被打通了，此时v1 v_1v
1
​       
就可以作为中介点连接。
于是遍历和v1 v_1v
1
$ b% g$ c5 r1 U7 j+ X) r​       
连接的点，例如此时遍历到v2 v_2v
0 b! G: p8 y8 z9 ~: p6 r2
$ |+ N+ C0 n1 p1 a​       
。
2 k. d% i4 u0 @7 [6 d6 r然后再以v2 v_2v
2
​       
' p/ N2 N3 z$ j) D4 A6 b 为基准，遍历和v1 v_1v
1
​       
连接的点。
( f9 a6 ^9 ^9 C& Q* F4 g2 B所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。



" b1 ]' \* U1 O* U# \2 c




2 `6 e* _* a# B* J1 y& u% }" C
9 `9 U9 F9 i* n- U& a这里的逻辑是这样的:
5 |1 q+ U2 }; F$ I/ w最小生成树
# e3 q2 u- C: J0 |9 v
" E: \5 {# W& D% l' x4 F* X: \1 f（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182