数学建模之图论

杨利霞

3 `" o" I% v" M数学建模之图论概览
% ]+ r+ j+ {' L$ z0 p( I! L
问题引入与分析
$ ^) z! J+ Y8 K图论的基本概念
最短路问题及算法
/ c# b  Z) x5 u0 h9 \最小生成树及算法
$ I& K, m4 p6 }$ P$ X" E旅行售货员问题
模型建立与求解
3 Z1 j5 W$ X: a$ r( B1.        问题引入与分析

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

  q1 l5 l( U4 ]) q' L今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
b. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
' x" R; v8 D: n( V
; B& j7 b6 Y) V3 h( U
公路边的数字为该路段的公里。

2) 问题分析：

2 m  j1 N9 ^0 t7 A本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
, ]/ U& z1 k. f5 Q# k! J- X% K5 I将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.

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

2.        图论的基本概念

图的概念
, Z5 N* F2 K8 {8 n0 Y8 m" c赋权图与子图
0 V' A3 g* Y' V7 v. N图的矩阵表示
* e, }( ^0 R/ s% N# t1 Z+ A图的顶点度
  ]# P! c: ]  S路和连通
1) 图的概念
5 ^; @; P, a; c" C5 j
3 C" P# j' j: i# z2 @
! V) _! P. K+ `8 W( ~9 Z# E
8 [3 o' }. ^6 ?! \% t
; E& p. O1 w; U% S4 }# w. H

$ Y& o; |) _2 N# Q; U0 r* O) ?1 t

0 n6 d# X% F7 b8 K) k

  T7 y9 `# y/ H4 q0 r

! |& d6 [) `  {

! C- Z  d6 O/ P2 F

+ C: A5 h3 |' l2 Z4 r: T

& W: Q/ q9 r, s% s9 M4 ]+ {* l3 ~# b

# e4 T8 r/ B( L# E. t
# X) K4 W$ H2 {: Q$ Y' G: t
, m, F' w. O) c; v



6 `8 G  I) Y4 F2 J- A# _



3. 最短路
6 x$ R6 s: D; U6 H
% G2 R' C* ^5 \Dijkstra算法

略
- p0 l/ b8 j7 e( d2 y$ Z. F* \+ @3 r
* O2 S; P7 w) p0 F2 U* SFloyd算法
, Z; z" g/ \; E2 U0 `3 [4 j5 x
算法的基本思想
8 n) [/ z) X" J5 V& j1 l
2 }4 u2 u/ m8 y- N4 T' M直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
6 e( z7 [# `! P9 F5 g1 @0 t* r8 r) K; S（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
（III）查找最短路路径的方法.
+ R( M: {9 ^( C. V& P7 O
5 S4 Z; A0 y  k. n& p3 sFloyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
9 w. p7 ^* w  E; f+ ?/ q
& Y# o8 {$ K- r  d! e  L
9 ^" H' |8 \8 S" {  i4 K5 e

. S- g8 V" A' n  _8 D+ Z2 I在这里相当于v1 v_1v
5 L1 |8 L, b; M4 }9 l. C1 A& S( i! G1
​       
7 E$ W, d9 v) V7 m7 e 被打通了，此时v1 v_1v
0 z- c5 y6 W0 Y' L8 A) w+ G2 I1
+ V  `8 b# J+ ^: w- n: S( c​       
就可以作为中介点连接。
  T5 s5 b9 E# N7 n1 o于是遍历和v1 v_1v
1
​       
4 ?% P) ^# q# J% g 连接的点，例如此时遍历到v2 v_2v
2 `" A  ~0 _2 Y) _6 f2
​       
$ P0 I- D6 S7 A7 Z3 _& J5 g 。
然后再以v2 v_2v
2
​       
为基准，遍历和v1 v_1v
1
​       
连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
. i% i5 [1 I9 C5 ]
+ w- L" k1 T, w; @- {$ Q% U  X
9 w, ?6 e$ F& E5 U9 b6 ?






0 @5 F1 m5 ~, i) H$ A* v- H2 G" z! Y这里的逻辑是这样的:
0 N8 G3 j& u; I" Q最小生成树
' ~9 i+ D3 O+ d6 ?' U
（略）
) S( u+ K( P; O! G. W————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182

+ b$ Z; U& b' d) D$ j: t4 }
6 g1 E9 q7 h% z3 c