数学建模之图论

杨利霞

数学建模之图论概览

问题引入与分析
图论的基本概念
最短路问题及算法
# M9 }: o% I5 u: N& G最小生成树及算法
旅行售货员问题
模型建立与求解
% a" D+ V5 U+ U2 ^' B% {% M( `, o1.        问题引入与分析

1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：
1 g& h9 v% o/ _6 T2 c% ?+ ]
" K' d0 [2 }7 e4 J+ Z2 W今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
b. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
  s- a4 s0 h2 P2 ]4 ]% m4 f

公路边的数字为该路段的公里。
% \2 S3 f) \+ q; O9 O: r
2) 问题分析：
5 ]5 B, T4 V$ L( n8 x: ^
本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
; z* u5 E6 e3 m: P将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
再回到点O，使得总权（路程或时间）最小.
9 n8 d$ f8 F% T' p2 t1 ?
$ P4 M& D  o1 d9 f$ m本题是旅行售货员问题的延伸－多旅行售货员问题.
9 r# o$ [" l; Q! y, _本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
' j% X2 F& `" t7 q; H9 s9 n( x2 s0 j% |如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

2.        图论的基本概念
" x5 O/ w- b7 _5 p% e
; \3 ^* @' ~9 C' M9 w: f+ Q1 p! H图的概念
赋权图与子图
3 V+ h& ]  C/ ^图的矩阵表示
3 F  p/ Z# h* r/ {6 Z$ R图的顶点度
路和连通
7 d. B/ T5 w9 v7 H: ~% ^* G1) 图的概念
: j2 k0 _, J1 ^) W" e4 Q! b; V& k5 `


2 r+ I5 h6 _, _+ }9 |

' z8 [# r3 I9 S, c! L5 z






$ n8 @2 q5 x/ S  [  s
% r1 C2 v( m6 N7 S" w" l0 S" D
! ?+ ?3 H$ B4 ^5 T/ b$ I7 F
/ u6 M3 T; \: Q. W



! Y: n% W: B' u2 B. X
& w, s, r8 [2 v7 {

0 ~. J3 D, U3 {  g

* a. F# L$ J8 O' o
( M2 c- d$ Z0 d
  H; ]4 T1 b+ e
  ~$ q7 k- f+ |; O4 v+ w+ r


% ]  t* E: d% ?" @3 G3. 最短路

Dijkstra算法
3 [. l) i" V* o0 ^
略

( M) z0 S$ E- ~Floyd算法
( |- ]4 u- l' ?' z9 i4 G8 B- B
7 ~4 s5 {# T7 d6 R2 Y# K算法的基本思想

直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
1 v* ~, q' g8 a6 D& ]（I）求距离矩阵的方法.
& b1 K& W; N6 K' G1 O（II）求路径矩阵的方法.
! u9 W& }9 w; l3 w（III）查找最短路路径的方法.

Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）
9 |" t5 P& X4 n, o


) Z, v4 r/ @3 d- s4 _; e% o
* t7 K% R$ L9 c* \; N" U6 ]在这里相当于v1 v_1v
1
​       
被打通了，此时v1 v_1v
2 N) Q: A; `2 T1
1 A) {8 H( c6 E* Y: u+ a5 z1 |​       
6 p  D0 ^$ y1 f, C. n 就可以作为中介点连接。
于是遍历和v1 v_1v
1
​       
; ]: l( f* T% V$ x7 t5 `3 d 连接的点，例如此时遍历到v2 v_2v
2
​       
* [4 N" ^6 t) h8 y. I" [ 。
% ^4 ?1 u: F. O3 ]+ l然后再以v2 v_2v
. W3 s- h$ C  R& I; @: J2
​       
为基准，遍历和v1 v_1v
$ u& u0 G& r, e1
​       
连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。

; n$ m" ~- C0 q5 i) g9 z7 q( W, u) _

8 M6 c" ?# o# o9 B- m" ~6 }

/ t* O; b9 Y7 Z/ F
# [  X% _. o& |  h6 S/ B- a8 p' x

$ R( P7 u8 b: e5 s
" P5 `& k- k1 }: m4 f( q# A( |) E这里的逻辑是这样的:
最小生成树
& \, i5 a. P' ^
（略）
————————————————
版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182
3 {9 x: l5 O& C) N' a
3 W! e5 D; Q) t& ]