数学建模之图论

杨利霞

( L' b3 q" d& B1 k# ~数学建模之图论概览
8 e8 A9 T. t! s" ?; t5 x5 ~
问题引入与分析
+ Z8 g7 h+ n4 K( q( t6 V+ ~3 y图论的基本概念
最短路问题及算法
最小生成树及算法
旅行售货员问题
8 F: ?) P, P1 _: P模型建立与求解
1.        问题引入与分析

1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

4 d0 i0 M, F2 E* {# q今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
* W/ {8 ?, K$ f2 `! J& pa. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
+ v0 j7 \5 q, y, Lb. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
, [  s) A( A! \  n

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

' Z5 b' v) Q# U2) 问题分析：
, _2 t) m# t- F9 g  y2 C
" q! c+ a$ T$ e4 ^) [) z! u本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
3 `* F: B) W+ v将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.

本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
, Z$ V/ [, b2 \: W% s: O) e众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.
" t# G  l7 m9 a) z
3 s! }6 u) [& L( j/ l2.        图论的基本概念
/ N* f: [: S' J6 S, G. t
+ I& M" D! \9 [5 A! W$ E图的概念
赋权图与子图
图的矩阵表示
图的顶点度
路和连通
: D/ Y3 M+ H. J) V/ V1) 图的概念





3 x5 ^2 X0 f8 o  V0 P, r& Q

+ x) v/ E, S- y* C/ @

8 p5 p' C% D6 l/ ~& m$ R- ]: C

1 {/ M; G3 y# [# s
1 I7 ?9 ?! s# E
3 m$ ]1 A% Z' O% V



) X1 b3 F$ H# u$ @/ C: `
6 K7 i* |6 X/ Y9 N! l! U
) s( m# I$ Z. X- @, A" ~/ s
/ H. Q% A7 j& q/ L- b- [7 o
, q: L  E1 {7 D


6 p4 y5 v2 Y$ F2 ?( \

* g+ I1 \7 n4 S+ k7 e2 j( l

1 r) X- c7 x4 x4 g* C
0 ]5 U# _. y" ~. @6 W* @1 n6 Q
5 X4 Q$ G  S& d0 f& v) A3. 最短路
* b9 r( g% l2 L  U& k1 |
2 p! h' {8 S( G4 lDijkstra算法

略
  S" @( G, t2 k( r" N' N
Floyd算法
. l& c- a& M- V! L
) A4 v: o2 X# }" b( ?! _; \( Y- f5 _算法的基本思想

; t( P8 X, E* W# q+ ]: y) ]直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
+ s" `1 V" a" s6 L8 |6 h（II）求路径矩阵的方法.
（III）查找最短路路径的方法.
2 v  Q) h& b! m. ^6 `/ \" r' Z% ^
Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
, E. N0 Z' V. Z& t6 ]' Y6 w; V
' O) y) ]" o9 B


在这里相当于v1 v_1v
1
' p! D4 {) U3 D5 ~: [​       
/ f. [8 I6 q& E! c3 W 被打通了，此时v1 v_1v
  t1 X) R/ G$ j1
​       
就可以作为中介点连接。
" j* q- g/ D3 ^: K' X2 z6 ~2 o. n于是遍历和v1 v_1v
  v2 d) t' [3 E3 f' q1
​       
连接的点，例如此时遍历到v2 v_2v
3 U0 u$ H0 N: q% E& a$ G2
8 t7 K4 I& n5 H0 s( d! v4 }​       
4 \. ^! o$ x7 ~' O* Q& ]2 a 。
1 j, B7 d+ g9 m5 W: q9 e/ I然后再以v2 v_2v
$ e( v/ T- D9 }4 \  y% n2
​       
为基准，遍历和v1 v_1v
- L) I* B% v4 a1
​       
连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。

/ [  m( D  N5 Q& J/ N

6 V" r' l5 C- X, t  n" E5 h


8 X0 L. V2 P- R. I) Q4 B

0 Z  O: M7 r* j
这里的逻辑是这样的:
! ^: C) C! D. [5 a最小生成树
  _; C4 q6 v4 e) X
（略）
+ J6 t) g6 p# l( z6 N; _1 d————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
  I+ U4 z  l+ U9 {% ^; K: G% T  T
; |/ g; H9 p3 |% R  ~* @0 O+ i