数学建模之图论

杨利霞

( ]! T1 u# X& n$ A4 b- j数学建模之图论概览
1 U9 K. m/ X% H% ~
问题引入与分析
8 W' m0 }2 s  |$ w; i图论的基本概念
最短路问题及算法
最小生成树及算法
旅行售货员问题
模型建立与求解
. S/ Y) X4 n8 P3 w/ _9 |1.        问题引入与分析

7 b3 x# L  `( K1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：
: R) f9 Q: Z: a+ v9 ^! v2 a' E
- i' p5 a  z8 }+ K3 v- C今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
; ^+ {0 O+ Y/ E8 c$ k% ~a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
  ?4 m, P4 A$ bb. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.


/ l: j) K2 A- p; |0 @; H% k公路边的数字为该路段的公里。
" W8 ~% a! t; M6 |; M
2 a* K  l% {! n% i3 C8 Y2) 问题分析：
# t7 k- l! d& {# W! T# A6 ?4 p1 G; x
3 M3 @! p' ~7 V$ O本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
* D+ T% q0 |9 h/ P& `再回到点O，使得总权（路程或时间）最小.
; \5 c! @7 U* O5 c7 X$ Y
本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

2.        图论的基本概念

图的概念
: N  K4 I# S; U赋权图与子图
  x& U# u+ o( Z, m% ^% s图的矩阵表示
" r' n2 Z2 b& f: m$ l! d图的顶点度
" H# [: E& v+ w. C路和连通
1) 图的概念
6 a# C. B3 B: _0 _" N  h4 x

) V6 |0 Q% i0 S
% g) `3 u- A' U& e, C
7 w/ \  V5 r5 a

/ `- I* ]8 L0 r& [+ k
1 z9 t4 }9 x* R0 O
3 Q4 H, t! L, X
: V8 l; w& z$ x3 d1 L( F
, U, I- ~% T- T: \: p- x

0 `' q1 Q7 U+ }$ a. [& ]


- p5 r+ a0 i" W) l: U& i; K0 i
6 K; L/ j1 W& A. D% C/ _! h



; `" J7 A8 p& c/ I9 [/ e
0 ]/ g4 K) b  g. f- e
+ n1 {6 n. J1 R0 Y( L

! o- m3 P* Q+ [; {
% O& J# M, U3 A1 O9 R

6 ?3 }* ]$ ^6 g: v" v

" P" I4 M( M+ }0 H( a$ f8 u, r2 a
/ r4 H& N* B- Z# C9 z3. 最短路
, b: o; G8 w) J
5 ]% R5 x5 g2 D5 _Dijkstra算法

% E$ ~: X" N6 D) F略

. o) `. d7 i- Q) m0 Q. }. }Floyd算法
! c; S8 Y8 `" r' [' H; Z
算法的基本思想

- X9 O; e  y' Q1 H* w& J# d7 A- H5 j' D直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
6 m" @1 Y1 o2 f5 H5 _（II）求路径矩阵的方法.
' ?4 P/ ?5 D0 I, ^- ]' c, q/ X（III）查找最短路路径的方法.

8 t2 G- W/ m/ Y: V' Q4 [( ~Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）


' k7 k9 @9 O7 B
. Y6 o% X  a: E" y* q6 m, \" y
/ u1 \) [) ?' @在这里相当于v1 v_1v
3 Y8 ^2 q  I7 l: {1
1 ?3 ~# P1 P$ ], G* r+ ?​       
& C0 s- n* c9 a# a/ o7 e7 z 被打通了，此时v1 v_1v
1
8 g6 Y8 \9 i- z7 r1 D​       
: t! l) ~+ Z$ k- T  [3 T- ]  S 就可以作为中介点连接。
* \3 J+ A' U# q) Y于是遍历和v1 v_1v
9 c- V1 H; V) t0 W1
​       
4 s. z' Q% i* s3 {! [ 连接的点，例如此时遍历到v2 v_2v
. n' h' ~8 `5 F4 L3 W# f2
​       
。
然后再以v2 v_2v
2
​       
为基准，遍历和v1 v_1v
1
​       
3 U! i% f9 X7 l  ]# b& L( a& E  D 连接的点。
  b/ t4 D6 q$ j) b% d0 F9 O所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。

( O9 C$ Z$ i# N7 Q
! `; O% f6 x- c8 Z, ?9 v! ]; }
9 M" K, f! n* a8 T- p
0 C6 o1 Z  g5 z$ {  L" B

( P3 M  y, `1 x/ B+ ^2 A


这里的逻辑是这样的:
最小生成树
# d5 o( w$ p6 W! C# i. A
（略）
* s4 m) d2 V* z% z7 K! [————————————————
5 f" h/ u! U! j4 g版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
5 ?3 ^/ ~. p. J

: k1 W' E6 p, M  P