数学建模之图论

杨利霞

. ], x4 l& q* z% D* v数学建模之图论概览

/ h1 R; B; |: ~" {6 T) B7 u问题引入与分析
图论的基本概念
. n1 E3 e) g5 W  v, ^( C最短路问题及算法
. I8 c: n. |5 o2 H0 R4 \最小生成树及算法
  O; Z9 C6 P9 t! M9 k6 i% m! w- H旅行售货员问题
模型建立与求解
7 F3 U6 Z5 ^$ T; s. x6 N2 G1.        问题引入与分析
, h0 _% I1 L& z+ }
) ^! h% N! U9 Q6 }1 b$ R1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：
2 g7 J. C- A. k1 ^2 m% {
6 B4 L4 N5 Y/ l4 j今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
6 L* L/ D6 F' @; ]4 qa. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
b. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.


* L# \% O4 h7 d7 A1 I- j公路边的数字为该路段的公里。
" f# }3 L1 \0 P' P' I
2) 问题分析：

本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.
3 m# Q2 \' {; ~9 h5 ?8 u
本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
9 w: [# q+ K3 Z2 }- M  M) v$ h" H如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
. h! U$ [% l0 U( R) P显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.
9 s  {6 `! i2 `  a6 M# {
5 F3 w4 ^8 y1 }1 i& s; U- O2.        图论的基本概念
2 C# M0 b9 {, {/ p  z
图的概念
2 d9 b" u# m3 z8 i8 I; q) Q赋权图与子图
图的矩阵表示
3 b- c/ I3 d- ~: e4 V$ q图的顶点度
' _% V5 v/ @+ T路和连通
1) 图的概念

+ Z$ d0 R8 C8 P; U) z

* g9 U/ b' ?+ Q" Q7 ~


' T) z) y& M4 h- O  k5 \8 h1 U. M
# S' O$ o; y# a( F! d# r( |5 \
. T4 N: u, \+ W8 e; R

* Q. L* T4 b8 g: u


% v/ n4 f% ^+ c: q- o0 R! G: \' ?
# g3 t  W' r, z9 i" N3 G$ I9 H* @

" k: L# D: T- y$ p; C/ T7 j

% u1 \! i, K1 H3 ~, J7 l



' J9 `' N* D8 i$ Y

* i6 m7 o- ~# B2 l3 t! l) n
# P. E/ n5 P& L6 {0 H
7 ?- U0 c$ m1 E! ?" B6 v* g


! Z# Y9 n6 j, P7 j* P
' l; u3 B% u9 l) S" g( s3 x9 }3. 最短路
9 G1 n' B* {. j' \
2 f3 _8 H) Q1 N4 m) k/ G3 IDijkstra算法
+ X* l* G+ L" j! n8 x/ u
- F2 y) ^# Z5 `" c4 F5 R略

Floyd算法
1 |9 ~1 z5 Z% b4 D3 E
+ o( u0 c8 F3 ?算法的基本思想
/ b. p/ S7 X+ y1 Y0 Y( I4 i
直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
0 W  }) A3 n3 S2 A（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
; w2 l2 E) _  y0 ^& U1 V（III）查找最短路路径的方法.

Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）

6 h5 k3 g9 _5 n  f, d7 {$ }; Y
" T+ |% ~  H* h2 _4 ]( T2 L+ @1 Y

在这里相当于v1 v_1v
1
​       
; C( H# b6 z) S 被打通了，此时v1 v_1v
' V; N# I, u2 \1
​       
就可以作为中介点连接。
于是遍历和v1 v_1v
1 U- v; R# ]$ j6 z. T% E6 X% l1
​       
连接的点，例如此时遍历到v2 v_2v
& T; h0 h% w+ u9 [9 g; C* c1 b; n2
  Z( G1 o* u6 ]​       
。
然后再以v2 v_2v
2
​       
9 B; a9 F7 ]- K5 k* ], X 为基准，遍历和v1 v_1v
8 W: c  h2 i! u+ @, o1
​       
+ M! g; C% [8 B: d1 D 连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。

1 F  ~/ d7 P. N6 P




% q2 e# R) D. _% w- {# Q
  b. Z% b' V" J8 V) s4 D( r
* S7 Y) ~( B5 N! F
这里的逻辑是这样的:
最小生成树
& \: R  `' c: c# K1 V
0 ~( O  R: ?. P* w" F7 B; x. N: D$ k3 k（略）
' L1 B' p# I9 Z+ f6 B2 ]/ ~5 _————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182

" ]. t% z0 b- ]" V' X8 p
+ q0 G+ b# S1 {/ k4 L* ?+ b