数学建模之图论

杨利霞

- g- Y- C6 _$ O数学建模之图论概览

问题引入与分析
图论的基本概念
$ z* L2 `' ~1 h: c# A$ T最短路问题及算法
! E8 F- l4 D4 t- I3 }' I最小生成树及算法
1 ^8 K1 N7 O7 d% l: F  O旅行售货员问题
8 y! y( h# {- L+ [模型建立与求解
1.        问题引入与分析
0 Y: F' P# q0 o) D
% \9 {% w' Q1 a4 p" Q. Y, Q1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：
" ^$ C" X) _0 W* Z
今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
4 u! v- p7 C: g: a5 d' k! {, pa. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
/ l9 ~! E' q1 ]5 tb. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.


- l' i% }1 u3 x公路边的数字为该路段的公里。

, E( D' o! q: W, m2) 问题分析：

本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
/ n: N) i- F: H& g" G再回到点O，使得总权（路程或时间）最小.

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

/ L$ T- v' V% B2.        图论的基本概念
' O9 N; C( w: A9 w2 h8 s
* S5 F. m+ S, k图的概念
' O' A( P+ g' ~, @赋权图与子图
图的矩阵表示
图的顶点度
路和连通
1) 图的概念
( \: f1 D; Z3 m7 n


% v2 N; p7 ^  S7 N% R9 N" @( a7 L
) S" N. }( O) [- H

* f/ n2 Q5 k0 F5 r) o3 p

- |) d' W( C! {( y6 s
% |# o  X( W5 _' ^* w+ [- L



6 y- K& c2 H' [! \( O2 N; J
9 D/ ~* o! H! O1 T) @




% u( M% O* k; i8 ], c7 j% a2 u+ h
4 `: t8 }  R8 u, X" w

! s& g* R0 s- z  X

9 j, b+ N$ ^5 `, T





' l' S  u  C2 i; ~. M- e3. 最短路

Dijkstra算法
8 d( C8 T6 g$ g$ f" Y; t+ K
  q$ u" R- U3 S/ N略

2 M: N% u  h1 y, w. b* U* D& O7 f( R4 LFloyd算法
" L  Y# N' K/ l
算法的基本思想

直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
) O6 d- @, ~) _! o（II）求路径矩阵的方法.
9 T2 o8 A! }* N5 u( U+ J1 k（III）查找最短路路径的方法.
% A$ D) j0 w6 w
3 i- G1 G( T' h! g! jFloyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）


: ?) K. |+ R% a# O4 P" r8 E" b

在这里相当于v1 v_1v
1
​       
被打通了，此时v1 v_1v
" ~: C9 ^, ~# g+ A, M" g" \6 ^- t1
​       
$ c* t: M' y2 c- x) O& q 就可以作为中介点连接。
于是遍历和v1 v_1v
) Y, [2 l3 E$ x! u2 S; y1
* B) a* ?/ P# k5 B7 N! D​       
连接的点，例如此时遍历到v2 v_2v
2
​       
* Z1 s  M! l! u; `7 g9 ]9 E 。
/ N% ^1 [# D8 R% p% S" l$ ?然后再以v2 v_2v
4 K$ U0 y7 B& s! A2
9 Z# F7 n+ f/ [/ u  g/ |" u​       
为基准，遍历和v1 v_1v
1
" H, |1 E: I9 X& U0 _$ [. @* Q​       
连接的点。
- ~" u, m: y! h% w, |  Y; z5 h+ U所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
% O$ T7 c9 i9 O- W" A# o( C' y


! H0 B, d7 o7 p( n( f$ W0 Q
& @) g1 h" i9 |) O# W

4 t  S* R5 A7 D' V8 P. \

6 l7 x3 j8 @& }* w% [" d* p2 r6 N
这里的逻辑是这样的:
最小生成树
. ^# g2 k  f6 @6 Q  F% \
6 ]9 O9 c! N4 a（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
( g1 m+ C0 j. `4 G. K$ r
: ]6 \: F. g8 h$ G6 U3 F