数学建模之图论

杨利霞

数学建模之图论概览
1 q3 E3 G" c9 |4 \" \3 V2 W
问题引入与分析
图论的基本概念
! D# ^  {' _. b. B# G1 `9 w最短路问题及算法
最小生成树及算法
# K8 N6 i0 M- p: a# c; }4 J旅行售货员问题
模型建立与求解
1.        问题引入与分析
1 X: }; u8 E2 \* ]! B
1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：
  q$ a, q8 C( Y6 G
今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
b. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.

. O/ l6 L& k! e( I
公路边的数字为该路段的公里。

2) 问题分析：

  K+ Y6 `: F% W; W1 e8 w本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.
7 r7 e. x, f$ M! k
" V& E. u9 f  F. Y! k$ |本题是旅行售货员问题的延伸－多旅行售货员问题.
9 U8 G9 c! S9 X4 b  u' Q4 X本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.
  E' C* [7 ]; l
+ z6 g% o7 b% C7 }) l4 G1 f2.        图论的基本概念
4 c( g! Z: g: x/ a* N( M
3 \$ B0 x9 |! {8 {6 \! [( m图的概念
赋权图与子图
图的矩阵表示
图的顶点度
4 _, ~) `8 v0 y( g& N2 f路和连通
" l$ B* D, R+ q* X5 F, S; V1) 图的概念

( F! U0 M( J! R$ b: u, v& S




& d% i/ x  h# ^6 c) B- T3 m1 l

8 M: E& y3 v+ M: q
/ ?/ D3 K/ W/ \$ z+ K% C! G" a

! e( r- Q% T, G6 N: d1 C





2 ~, U3 f( B; I2 r$ Z1 k  N
, N5 T% B! B2 M3 N


% Q, X9 t. k; l$ a% J) b! F/ l, M
: k9 O$ P' m8 r) [3 _" z



$ O" E+ d3 ^( s# Q2 m; Z: [
# A( R$ x8 |* x) _# u

% l5 b: U: U) }: c! k  K- ?
+ D  Y& O9 E% ?& ~3. 最短路

Dijkstra算法

: Y, V8 o: r- B9 O  @4 d略

  h; u" |9 C1 x/ pFloyd算法

( _5 W, V; ?( i" J* Y- Z算法的基本思想
2 n$ C( j+ s$ X
直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
+ W* I" c! @1 V# i+ E$ z5 }（II）求路径矩阵的方法.
（III）查找最短路路径的方法.

! Y3 ?* f; a8 j# V# y5 H7 N. TFloyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）

* N; U2 n+ B/ x! h
% Z, G# F9 ?; u4 q
( D3 G& ?6 C% u7 \0 d2 A) o
! v( w* c- U! Z2 l8 L& o0 \在这里相当于v1 v_1v
; @6 L& j, H' E8 c4 L1
# X6 t# O  c8 a( V! T- p1 m. y# f/ @​       
3 u" Y! Z# `- ]5 [+ z 被打通了，此时v1 v_1v
6 A: @; a& |& l/ h" n: y# e1
0 X$ W/ a! m6 P! r; D​       
. P8 q2 A+ n7 M' Y/ D. \ 就可以作为中介点连接。
于是遍历和v1 v_1v
1
; \9 u5 j: H8 K, ]# q: a" }" l​       
/ G" t, A( _: M8 F% I 连接的点，例如此时遍历到v2 v_2v
2
7 {; w4 [% \9 [​       
8 C# X/ ]7 r/ n+ A5 X1 Z 。
然后再以v2 v_2v
2
0 E0 r/ A0 T  m: h​       
4 L+ G6 M8 U0 D, l% |- h! P; b 为基准，遍历和v1 v_1v
1
​       
* o4 e7 O2 \( h( n3 E: i 连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
' j0 W3 M) Z) Z8 x0 l& A9 H/ R
* D' n/ _. t: v" B( n) S



/ d7 s+ u8 i3 {- e$ B: ]
( o, w. G7 `, r6 z) Q
( `6 N/ \! W1 W8 V) |- `
2 E2 m+ g7 S1 w- l  M  _7 e0 j
( P) h, l/ `8 J这里的逻辑是这样的:
( N1 f7 P0 z4 W& Z最小生成树

（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
% k9 A3 l, w+ [
1 ^4 F9 P; n/ g( T) }* |0 ~
' X; N% H1 Z% R1 v