数学建模之图论

杨利霞

数学建模之图论概览
9 z- `9 G2 M1 R" @1 n2 i
问题引入与分析
5 J3 m2 m: C* o& o; G图论的基本概念
最短路问题及算法
8 Y- l6 E: `0 U, E- L最小生成树及算法
% k7 K& J9 Y/ N5 Q8 z旅行售货员问题
: `& Z! Y/ l. y& O4 X模型建立与求解
1.        问题引入与分析
0 j# Q* R9 [4 I3 h
1） 98年全国大学生数学建模竞赛B题“最佳灾情巡视路线”中的前两个问题是这样的：

今年(1998年)夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.
a. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
b. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.
7 D! S! W+ R; u! B9 K3 ]
7 ?) D8 V0 o" d7 X8 }
. b$ o0 }% P! l公路边的数字为该路段的公里。
" O% @% c0 O3 {
6 h" {: {9 \1 y" D1 I0 O- @2) 问题分析：

本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线.
1 J# S$ y4 N4 L$ D5 y将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次
* g7 M/ K% V( D7 z再回到点O，使得总权（路程或时间）最小.

本题是旅行售货员问题的延伸－多旅行售货员问题.
本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.
如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.
: e+ P, T# l+ A  I7 q5 ]1 w' u8 x" U众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.
$ c- Y" R2 ?* b* y3 r  e显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.
3 s/ V/ @: C2 Q1 o. Y% ?. e
2.        图论的基本概念

6 X# }  M: Z, C- `: C" v图的概念
赋权图与子图
图的矩阵表示
图的顶点度
2 A, ^4 Z' a+ Z* w  X0 y& ?路和连通
1) 图的概念

* |+ a$ e' g8 ]2 @6 y; S
4 C: h" h0 E& u; y: e7 h# o$ R# a% w


% k7 M% N4 F: b) d+ J, t5 H1 O
' V% X, c; r: g  b) T8 j
. {' b/ k1 [' |0 j5 }, c4 U
! h* v1 Q2 c8 [1 q, N



6 x, F" K7 T/ P7 ]/ e, y
1 e- s/ Y- @9 u& F' s( f; n

3 _% G4 t( I; U& \  w1 X3 M
; w$ o: c9 |9 ]) _" O! k- U



; g5 r( ~3 i' T- S8 @7 V& }+ s
/ n. K% k- ~# ]

( k2 p  y1 l) U

. z, m% C  l, W" J



1 z8 b% C* I% f8 `' [# N  N8 \; G- X
+ _  g1 w, c7 ^* a3. 最短路

$ _. k$ p6 L$ r. }) CDijkstra算法
& F* Q# t+ b6 M3 d
, W; l  _/ J0 w  G* A/ ~" S1 }略
  g0 g$ `! b$ X9 N- c0 j
Floyd算法

4 y; ~/ }9 A$ [/ u算法的基本思想

: u6 D1 Q9 t/ c& J! _直接在图的带权邻接矩阵中用插入顶点的方法依次构造出ν 个矩阵D(1)、D(2)、…、D(ν) D(1)、 D(2)、 … 、D(ν)D(1)、D(2)、…、D(ν)，使最后得到的矩阵 D(ν) D(ν )D(ν)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径。
（I）求距离矩阵的方法.
（II）求路径矩阵的方法.
' O2 l5 I; U' x（III）查找最短路路径的方法.
$ D% k' M# m9 S% H9 C
Floyd有两个矩阵，一个是D矩阵（代表距离），一个是R矩阵（代表中介点）


* w  {/ A  x) h" j) z( h7 ^/ i
$ g! U; I. r& R8 g) u. @
在这里相当于v1 v_1v
% I9 N+ p- l& I& L9 O/ F" W1
​       
5 Y! B( {: u  m+ g 被打通了，此时v1 v_1v
; B* T; O( M( Q" W* g) k( q# P1
1 z' {: c* p6 m) h, @' T. D5 ^​       
6 b) s/ F; w0 |6 J$ U 就可以作为中介点连接。
6 N- M0 N$ @  G* B* c于是遍历和v1 v_1v
! d4 N! u0 \0 p1
, A9 W8 z' A8 x& z2 n0 O​       
连接的点，例如此时遍历到v2 v_2v
2
% s; ]3 d1 I: z! v/ [7 @& E) F​       
( n$ \; B  p/ r/ X3 p 。
. b% @6 k8 q* e  t然后再以v2 v_2v
& m/ ~% W/ W$ K6 z- Q' a2
3 x+ q. h% A6 H​       
1 x" M, u7 \! K 为基准，遍历和v1 v_1v
8 _. }: b( ?( E% h1
( u$ o; R4 d0 \; _​       
连接的点。
所有遍历到的点都尝试一下是否可以变化距离矩阵，如果可以变化，那么再他们的中介点矩阵上打入"1"的标记。
' {! V3 b' y; w) P5 U
/ E8 r6 L+ @5 b! p) u/ v, Y

+ N& m, F( M* W% i, s
; ^6 E. m* ~. e1 o! T  {9 J" t
0 V5 A3 X0 z  t5 s0 R8 s# G9 W



这里的逻辑是这样的:
. O7 q5 Y1 M/ t7 {最小生成树

1 k! \" S) z0 Y: S1 P; w2 s（略）
$ b* i- P) F6 H————————————————
" F0 S8 Y& b! ~' j版权声明：本文为CSDN博主「Mr. Water」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
& e/ y* v! o, N$ p) U+ A8 H: f原文链接：https://blog.csdn.net/narcissus2_/article/details/100022182


, _* K6 V, A0 Y7 }