数学建模之图论

杨利霞

6 s, Q; ]; h( W4 X4 ]+ R6 o' G+ d数学建模之图论概览

7 B1 x9 c$ v0 o: f5 T% Z- h0 i问题引入与分析
1 A+ g* ~0 J& J; l图论的基本概念
7 U- p6 N* Y7 Z) |  a0 Z3 G最短路问题及算法
最小生成树及算法
. g0 o( W2 P, s3 T' z+ f7 G1 v旅行售货员问题
! L" q# Z+ W. q6 d4 T0 @1 G模型建立与求解
1.        问题引入与分析
5 \8 H, p. P- u5 B
1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

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

7 |2 y0 q( t7 i7 e$ f
公路边的数字为该路段的公里。

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

本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
$ o/ G$ C% P5 \+ B3 D$ ^如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
0 u/ N! D8 `2 ]# K, p" ^众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.
! x6 a- ^) I$ `
2.        图论的基本概念

5 x! k/ C3 ?  h  I图的概念
9 q  C. M, P' b: R+ Q) X" y赋权图与子图
图的矩阵表示
图的顶点度
, K+ m9 |, _) Y( e% F+ O路和连通
1) 图的概念



& Z& j+ @( \5 P4 N
' K% t) U. f4 ^* r" Z; H  |0 u
4 {: E2 G4 {# v8 J+ ]6 A
9 y! W& n0 O5 F% f2 e3 q# n

" I2 }; Q0 U3 Z1 N9 B8 X
) q1 t% T: w) \

$ |: D7 \& E8 Y5 R. J2 E



1 B' D; V% U8 ~& P" ~8 x



/ e1 x; U: k5 y+ Z) X7 ^


; q# l% H8 w- ^0 Q0 c' K; J; q




8 \% T& M* c* {$ G; V7 v8 ~
, e# {& M3 g' |* x! N+ `

3 E( s7 [+ q, p# l8 E3. 最短路
3 `$ w  T' ~; |$ b6 y
+ K& E# q; x( f, QDijkstra算法

: f" x8 D0 N- I9 V略
" ]/ ^/ ]3 P2 f9 A: i8 {. v  q
Floyd算法
! t4 n3 N, @& _
5 B5 o# w. g* i算法的基本思想

( }7 t. ^- r0 c( @/ |+ ^直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
+ d5 f5 g- C+ V8 P  G8 G) C- |（I）求距离矩阵的方法.
1 z- ]2 w# u  t（II）求路径矩阵的方法.
（III）查找最短路路径的方法.
3 t  g9 D7 }0 H, r
Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
' U4 p$ @" u1 O! T. _; `



! C& C* C8 N1 O3 n8 S在这里相当于v1 v_1v
1
​       
! i) L4 U2 o' S* `3 G 被打通了，此时v1 v_1v
0 x2 C6 k9 B& }, K1
​       
2 Q. r: x. ^2 [& Q' q: y" R5 D 就可以作为中介点连接。
于是遍历和v1 v_1v
1
​       
连接的点，例如此时遍历到v2 v_2v
2
- ?, V5 k& t# o# |8 m​       
。
+ r( ~( [/ D; h3 p7 R然后再以v2 v_2v
# _( h$ A0 j% O" F3 l- G2
​       
! v" H' o# g% U; r; o5 a6 z. X 为基准，遍历和v1 v_1v
1 Y! b7 V( M' n- ~1
6 @! O& T' l' Z​       
1 ?- ~7 h& ]1 F0 r4 v4 L 连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
) w* M/ C- P5 G) Y
& r. L/ e9 C  U$ @


( h% S! Q5 f! P" ~% B4 N$ X' t
4 g; B6 S$ F' i: j; M
9 O8 K) F, S8 h# ^0 h- x% g6 y
/ V) j" x. Q; D( V+ K% i8 g% M

这里的逻辑是这样的:
1 `# }5 w; ~! a最小生成树
! M: Q, @4 y$ e- \* r% t' h
# `  W+ @8 v  n5 M* k. Y& A% r8 q（略）
7 P  \6 i: G# j1 z& [9 x$ `————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
& m! D) U( x9 C$ N8 {4 p. d