数学建模之图论

杨利霞

数学建模之图论概览

. |& n4 V3 V7 N+ l2 F6 L问题引入与分析
: ?- l; P1 \, J图论的基本概念
最短路问题及算法
最小生成树及算法
旅行售货员问题
6 [9 k( c0 v: ]; |4 }模型建立与求解
1.        问题引入与分析
5 [6 z1 [' j2 y
1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：
! [) @" T  m" G+ V
今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
1 V7 i. k- n. p+ y8 X5 a2 ob. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
/ h9 p* ^4 M+ M8 x0 t; m+ y
$ @/ y/ v2 e1 o7 P$ P1 v3 b
' y$ i" u* b6 b. o, t+ m公路边的数字为该路段的公里。

2) 问题分析：
0 C6 l: U# B" _4 y1 _; t
本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
+ j5 t' B0 O; `1 J' [8 G2 I% Q再回到点O，使得总权（路程或时间）最小.

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

2.        图论的基本概念

图的概念
赋权图与子图
0 u: f. R4 e8 n' _图的矩阵表示
, g# a; a* z& h3 F" F图的顶点度
" n: R. ~8 ]+ t3 N. W$ {* H* n, z路和连通
1) 图的概念
% _% g; l# G# g, G6 v& j


$ N7 I; O9 z% e, Y; u' |& |


0 {5 e9 k7 X) _, U- X. o

  c6 j) h  n6 G7 J$ @. U4 J



; U' F6 I! A2 i, i# s- c
/ e  q- \# _$ E8 i5 F+ }


, l# s+ |: H7 f- h7 J$ j' O
! j0 x( Y; t- s( D. E2 l
  k7 ~1 n( B  O1 o7 B$ k
: ~9 Q4 L1 {& l8 e( O3 R3 [9 T

7 s- [7 p7 ^& _) k4 I% S. F
/ x4 @3 R. r0 {& q

, r: S- B7 a8 i, p0 p/ T
' N- w7 B# K& j
' ]( T2 ^( Y1 }* ]4 D3 F

4 R8 `$ e' B3 M. Z

% t! Z5 N; O5 r; \3 p3 u3. 最短路
! l5 k3 q# x" Z7 w9 S/ E
Dijkstra算法

略

Floyd算法

) [" I. @8 a1 Y( k. S. h- c算法的基本思想

) A! b4 \9 ]5 o" s; z$ C# i+ U直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
6 j: T9 |2 w5 v（I）求距离矩阵的方法.
7 N! e( g  U) [: @（II）求路径矩阵的方法.
（III）查找最短路路径的方法.
+ a  L& q* J! W
5 |* P" J) s! CFloyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
7 B: z4 p8 b+ N9 x& O

/ R' D8 W6 R) j
8 M7 L+ L- Y8 d; S
在这里相当于v1 v_1v
1
​       
4 w  v. ~, Z: d: a9 p: a 被打通了，此时v1 v_1v
1
. J  v- B) q" P8 h​       
就可以作为中介点连接。
于是遍历和v1 v_1v
/ [! ]) t% ]; p" X: l1
​       
7 i( p/ o, f4 g% x' z4 W7 U) ` 连接的点，例如此时遍历到v2 v_2v
! Y5 `4 L" n1 c2
1 ~& p  t: E9 F. x, y' o$ R* m& V​       
: l$ w  O4 Z# _  a0 a 。
然后再以v2 v_2v
( L# I: Z- |# k7 l: c9 t2
​       
8 O; s4 Z. A4 l1 U. [) u 为基准，遍历和v1 v_1v
7 F1 @' W3 O' z( ^1 |' \- @3 i1
​       
. K4 w2 Y0 k* s( E2 b 连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
  N* R  U8 N% c) s8 }4 ]

- j, v# V* U: E  l, J  z% H1 x8 G, z
  V$ n' Y) f2 {
. m& h3 `$ x5 o" }: @
, Y, m3 `) s8 F0 z8 x7 P



这里的逻辑是这样的:
& u/ R; K+ g" v最小生成树
. @* Z! U- I; M, Z+ f$ B* w
0 W$ E+ H! }% K（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
" b& D* [* K4 H/ t; g6 j! T原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
3 [( G) X4 m0 b/ {) a