数学建模之图论

杨利霞

0 a# k8 u- Z$ I. N数学建模之图论概览
+ g& _! ?+ F  E/ \% }- R* [
9 Y5 Z! \/ ]. z问题引入与分析
图论的基本概念
最短路问题及算法
3 B& e! |6 H3 [! f  N' R+ K最小生成树及算法
旅行售货员问题
9 ]% L3 E6 w, l' N模型建立与求解
# z4 u. N8 s3 u6 \* ]1.        问题引入与分析

. Q1 L+ F$ j  h; C2 k1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：
& [( x. H( ?3 u0 n
今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
1 S7 z, w- l% T- Y: C2 aa. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
b. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.


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

" W, v: i1 X. M7 v2) 问题分析：
( O; e+ M, r$ p; G8 r
- G8 h& ]4 u! D# ~# ~本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
, u/ E7 a' C: R& ?6 v将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
& f, ?3 t4 Q* M% Q4 t再回到点O，使得总权（路程或时间）最小.
; i1 V6 w2 u  v6 O8 E2 `
/ ~- h$ _. ]/ C' F本题是旅行售货员问题的延伸－多旅行售货员问题.
+ N0 {, h) ^. U本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
- a/ ]9 W# i& `- Q如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

: b& I  k+ P$ U0 l5 b- d9 I% G0 j2.        图论的基本概念

图的概念
0 T1 Y% n9 L$ ]( i# ?/ J赋权图与子图
图的矩阵表示
5 B$ p& D+ J9 A图的顶点度
路和连通
8 F9 y; D3 k' ]; \/ g' O2 {1) 图的概念
& ~8 U# F! L$ b/ Z1 {
0 A9 k( B0 ?0 @& y& R


/ G4 }5 `/ I! c" D" ^

; {) g0 o$ F7 e" N* W8 J

8 _- r! A5 J0 K8 `3 M" W) x; @
2 _% Y) ~: I  j' ~& k2 M$ x
; ?1 I- a$ `2 _/ C" J% B1 P


- }" N; \' f: I  \4 s

+ {# h$ d$ F- L6 J! A+ Z$ |; q
4 r7 |+ B% q, n0 o6 T2 m
3 E8 }1 J/ l0 y+ Z

3 L. h& j; Z9 K' `4 K




. q6 i6 F3 [3 ~* k3 j0 T! ?
* P; M4 j- v( ]% m8 Z
$ }3 i7 e3 T: ]7 y0 `

  V& E. l' K3 U, J# w

2 m7 t  c: J) a+ a# A: E$ m# {4 \3. 最短路

Dijkstra算法

# g) g2 \2 s& K0 Z) Q/ |: F7 J略

& D) C" S; h5 m9 n; Z5 LFloyd算法

算法的基本思想
- d- c0 e: D( S. w& w" i/ F
直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
" n2 C+ Z7 D; q# a9 O（III）查找最短路路径的方法.
: Z5 n- L9 y/ V& o. _) Z; l
Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
( L* D4 X, ^7 X! Q$ b
5 j. k: m; Q( \8 X! X9 o


! y+ g  ~0 }# K) M9 n" S在这里相当于v1 v_1v
1
7 ^5 E9 k% D" }9 Y​       
被打通了，此时v1 v_1v
1
​       
4 Y6 }& _- p0 @4 `( [ 就可以作为中介点连接。
+ u# j. q; H6 `- O于是遍历和v1 v_1v
. c  a" l  t7 B' d4 }1
6 s/ t9 |0 ^6 ?1 R  \9 O! C- F​       
0 C9 e9 Y0 V0 Z 连接的点，例如此时遍历到v2 v_2v
, d" Q4 o; u* M( p0 R* {* C; m+ p/ A2
: m: h* q& n0 Q3 J( `7 E' C9 {​       
。
1 B" U, p8 f4 k* M  ]然后再以v2 v_2v
2
5 d  D9 h# q5 I- l4 A​       
( O0 W) L2 Q( y  P# \6 ^+ W: j 为基准，遍历和v1 v_1v
1
​       
连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。

* a% _5 Y( a5 C, w

, a; J5 s5 A3 g

8 L; K9 V( x  v+ X



这里的逻辑是这样的:
( g/ F+ `- Q9 Q最小生成树
/ _: U5 t. u! h" g
- _" j% l4 u' N+ U: M3 W* U, \（略）
, U7 q2 c  i; s7 _: A/ s  ~( G# J————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
" m  ]5 {) S, Q3 Y0 _( }9 W原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182

6 H# K' A5 V( b, R  t  C8 `
6 O! Y: @2 r: @; N( q( l" S* M4 v