数学建模之图论

杨利霞

数学建模之图论概览
! l" \7 ^0 L8 \0 H, F
问题引入与分析
( c0 B5 ~8 V2 O: I- ^6 L' [图论的基本概念
最短路问题及算法
最小生成树及算法
旅行售货员问题
0 Y1 }  C3 M+ _3 G2 \9 G4 X% x  o模型建立与求解
  C5 i5 {  [" @- _  E# u- L1.        问题引入与分析
4 P5 G1 P1 ^& H; S: h+ [* R
1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：
5 q) L) r8 A+ D) ^* f# b8 w
3 a: ?2 G' U: Y; Z# v; w* P: x今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
, w/ f% M) Y, |; Z/ V5 k9 Zb. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.


) t  p9 T6 p: Z! C3 H/ [% e7 s公路边的数字为该路段的公里。
- D  A7 `9 c1 t& Q0 q
+ K" l; k) Y& b% _0 c# Z8 V2) 问题分析：
' x+ |  |7 p0 n# V
本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
7 I9 {0 ~7 {) E: L$ \- k再回到点O，使得总权（路程或时间）最小.

) p( Y  V$ N3 Y+ ?5 U" }; ]9 K! Y6 A本题是旅行售货员问题的延伸－多旅行售货员问题.
8 e( i, P' O' G* r! o. R本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

2.        图论的基本概念

, w# Z: ^* R0 W- I3 O0 m. Z& K  t图的概念
赋权图与子图
图的矩阵表示
图的顶点度
1 j! y% S8 D* e6 ~& y路和连通
& }- x- N! x& Y+ _  b+ L4 g1) 图的概念



2 O. p5 A! |) f  V
: U  Y' F9 M6 p/ N4 m( y9 G
  Q* R" K9 {, o$ f
. F# P% n4 B9 S* X9 E: T
; F8 [/ P: Q# [" N2 Q. G# w
  i3 ^3 }+ D! n$ j: t

7 t0 O, e4 r  v7 D7 O3 ?$ U


) e' \3 p2 V# P6 k9 w
# g7 [7 f1 v! I) @3 t
, Z' L' p/ C0 I2 k+ {( ~% k) e
2 U# r* q. g5 y# S# G
. l6 D3 H5 e! l# L0 B& y8 |( [
1 W6 D* V6 T* k4 J6 z


" ~$ l" C% ^* \

/ e- F! U( Q! G2 `7 Y, k8 C2 o
* k5 f5 u- ?# ?6 f  ~, r$ F9 z




. N/ z9 v/ k4 ~  L7 E+ w9 J2 v
3. 最短路
3 j# i; b( `# k" j- T* @5 A- n% M
Dijkstra算法
. g$ O) w- k7 m' j+ D5 R2 D% @
略
& w1 |1 W+ e% W
% Y5 `7 p/ x5 U5 V) v$ h3 D6 GFloyd算法

/ h6 i! J. c. D" G+ e8 p- P' ^; e算法的基本思想
2 z. N" W- @6 K1 m0 a1 L
& H8 T) d( K! o直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
/ m% w3 M+ `/ [8 y% l+ J（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
（III）查找最短路路径的方法.

' f. Q0 e  Q' V/ {8 SFloyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）

, E1 @& S( {) R, q( J


! V( T9 I8 z# u5 [) P  s7 ]- {在这里相当于v1 v_1v
) {0 y) b' P( H- @9 t$ Q: z7 n' ^1
​       
被打通了，此时v1 v_1v
: ]& ]7 c- K* ~7 w0 J1
( D$ _5 o( i( ^6 z: ?0 i6 J​       
' J+ d2 \' m$ u# `; H4 N/ R/ c 就可以作为中介点连接。
于是遍历和v1 v_1v
1
​       
连接的点，例如此时遍历到v2 v_2v
2
​       
。
+ A9 b. k6 j7 X5 k然后再以v2 v_2v
2
5 q/ T$ g$ L7 B) R+ r8 T​       
为基准，遍历和v1 v_1v
1
% W, t! n" D0 f5 j  z$ N​       
连接的点。
5 h, d' d  B9 A& T; C所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
4 o. R, D8 s' D1 h
# Y- }# T1 _7 p0 U: ~) ~
" H! @% P) L$ D8 R

; _! }+ i' }7 ]  I" c( c
% ~# z, c+ L: p+ N


( U3 M# o' @6 m  N  S# c' n% n
这里的逻辑是这样的:
* _, V9 A0 Q7 f$ i' Z9 z' X3 e最小生成树
. q9 }# f$ @( `+ \, D7 B
: N! d  Q* C& G7 M（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
: E& X( \7 A- Q6 ?* s0 v2 l/ e