数学建模之图论

杨利霞

6 Z: z2 j/ b1 m: l( i' P( Y数学建模之图论概览

问题引入与分析
图论的基本概念
. g& z1 F. _( C5 y) I$ ~6 G最短路问题及算法
9 W$ R& X1 M, o; J9 S: `最小生成树及算法
1 ^& v: }1 _" o$ b旅行售货员问题
0 h: I. h- h; b' u! ]0 G- a模型建立与求解
1.        问题引入与分析

* A% Y6 c" Q  h- A8 Z4 ~, {1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

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


公路边的数字为该路段的公里。

2) 问题分析：
# t& R" o  E1 B; e, x
本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
; Q9 g9 R! m1 R* ]3 h0 ~将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
; G9 w# d/ U. P- t再回到点O，使得总权（路程或时间）最小.

本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
& H! n" Y/ v$ }0 }+ n. l, L众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

2.        图论的基本概念
- N9 N5 S/ n3 n5 A* k
图的概念
赋权图与子图
图的矩阵表示
  [0 M1 O0 K9 d图的顶点度
路和连通
1) 图的概念

8 z1 C7 I% p8 M3 B7 g4 x
& s' p# R! |, I. i! ]( w
7 ?0 m4 @8 f* t* W, q2 a
, }6 |  r2 l" S: A6 k- [, [! ?

9 ?' i% v0 ^" N
3 J& {) {$ J7 x* `9 ]' Y4 a3 V
: j6 A% j3 j/ @* i6 _5 y

% X* J! }: k' i0 F- f9 A3 v


1 O+ b6 d8 G0 ^+ C5 d
4 y' `7 z0 |$ P* j0 ~& G
: w; Y* B; z, E# `8 k
7 y4 S0 c$ R3 ^5 S9 j
" ~: P! h3 Q- v; I7 G9 i# H
) `" c: w0 n$ y% f
$ M) l7 o* C" x2 p
, @3 ^$ s  d. Z3 t- _

. M6 [) k( h/ V( z$ D0 `, ?, F/ ^

9 z: ~9 Y2 }5 v! y: e4 h
- S) \3 i  L0 q, b
* X$ x( l2 H4 b$ X/ U


! Z7 E4 g  I% }) `  e3 G/ V
3. 最短路

' V' M  ^2 t5 @  v8 cDijkstra算法

略

3 b, }& Z8 O' N1 FFloyd算法

算法的基本思想
9 ^3 b) z; V3 a7 w+ m) o1 A9 N
直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
5 n+ Q" V0 t$ f" S! e" P& r" a4 r$ i- T（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
6 B  l3 l2 ~0 n" J7 M% z5 a（III）查找最短路路径的方法.

Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
2 n- Z0 C' G' f$ \8 K4 T
; M- q$ g1 q: v) ?8 L

. ]$ _* g% }- h
7 A+ E( Z+ \( |8 ?6 ~% y0 D在这里相当于v1 v_1v
1
( ?  u' }! x1 R/ s% k+ C  P​       
3 B; L% E/ G( q/ n" K' f 被打通了，此时v1 v_1v
1
+ |' a6 n0 `) T1 n+ i. O2 L# C​       
就可以作为中介点连接。
于是遍历和v1 v_1v
1
​       
7 s! j8 R( E2 K8 l9 \8 z 连接的点，例如此时遍历到v2 v_2v
2
  M' c+ x% h. c​       
。
4 F/ U/ m! I+ g8 [' d然后再以v2 v_2v
2
​       
. G0 _4 k4 K2 p! G 为基准，遍历和v1 v_1v
1
5 Y3 O: y4 W; E​       
# R5 ]5 E$ _8 _ 连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。


  P$ C4 ^4 u9 |

* Z1 _: n: Z- `0 d5 c+ @& ~8 v
, Q+ C8 r) S, U5 z8 k/ c2 A
/ |, u8 v1 K2 C; b
6 z  d6 [1 y, V  N7 f% h) U, B8 ~3 L
( m& L, l( B# v( n! a) m
这里的逻辑是这样的:
3 _9 h& F1 `2 ^最小生成树
# ^! C- C9 f9 G) n6 ?. L
（略）
————————————————
4 |* R* p, y3 d# }) G; L3 s版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
0 x% d# [, {8 S, T4 y. N: D* ?# }