数学建模与数学实验 最短路问题
实验目的1、了解最短路的算法及其应用 2、会用Matlab软件求最短路
实验内容1、图 论 的 基 本 概 念
2、最 短 路 问 题 及 其 算 法3、最 短 路 的 应 用
4、建模案例：最优截断切割问题5、实验作业
图论的基本概念一、 图 的 概 念 1、图的定义 2、顶点的次数
3、子图二、 图 的 矩 阵 表 示
1、 关联矩阵2、 邻接矩阵
返回
图的定义定义 有序三元组G=(V,E,
)称为一个图.
[1] V= {v1 , v 2 , , v n } 是有穷非空集，称为顶点集， 其中的元素叫图 G 的顶点 . [2] E 称为边集，其中的元素叫图 G 的边 . [3] 是从边集 E 到顶点集 V 中的有序或无序的元素 偶对的集合的映射，称为关联函数. 例 1 设 G=(V ,E, ),其中 V={v 1 ,v 2 , v3 , v4 }, E={e1 , e2 , e3 , e4, e5 }, (e1 ) v1v2 , (e2 ) v1v3 , (e3 ) v1v4 , (e4 ) v1v4 , (e5 ) v3 v3 .G 的图解如图.
定义 在图 G 中，与 V 中的有序偶(vi, vj)对应的边 e,称为图的有向边(或弧) ,而与 V 中顶点的无序偶 vivj 相对应的边 e,称为图 的无向边 .每一条边都是无向边的图，叫无向图；每一条边都是 有向边的图，称为有向图；既有无向边又有有向边的图称为混 合图.
定义 若将图 G 的每一条边 e 都对应一个实数 w(e),称 w(e)为边的权，并称图 G 为赋权图.
和 分别表示图的顶点数和边数. 规定用记号
常用术语： (1) 端点相同的边称为环. (2) 若一对顶点之间有两条以上的边联结，则这些边称为重边. (3) 有边联结的两个顶点称为相邻的顶点，有一个公共端点的边 称为相邻的边. (4) 边和它的端点称为互相关联的. (5) 既没有环也没有平行边的图，称为简单图. (6) 任意两顶点都相邻的简单图，称为完备图，记为 Kn,其中 n 为顶点的数目. ( 7)若 V=X Y,X Y= ,X 中任两顶点不相邻，Y 中任两顶 点不相邻，称 G 为二元图；若 X 中每一顶点皆与 Y 中一切顶点 相邻，称为完备二元图，记为 Km,n,其中 m,n 分别为 X 与 Y 的顶 点数目.
返回
顶点的次数定义 (1)在无向图中，与顶点 v 关联的边的数目(环算两次) 称为 v 的次数，记为 d(v). (2)在有向图中，从顶点 v 引出的边的数目称为 v 的出度， 记为 d+(v),从顶点 v 引入的边的数目称为的入度，记为 d-(v), d(v)=d+(v)+d-(v) 称为 v 的次数.
d (v4 ) 4
d (v4 ) 2 d (v4 ) 3 d (v4 ) 5
定理1
v V (G )
d (v) 2 (G)
推论1 任何图中奇次顶点的总数必为偶数.
例 在一次聚会中，认识奇数个人的人数一定是偶数。
返回
子图定义 设图 G=(V,E, ),G1=(V1,E1,
1 )
e E1 时， 1 (e)= (e),则称 G1 是 G 的子图. V,E (1) 若 V1 E,且当 1 特别的，若 V1=V,则 G1 称为 G 的生成子图.
V,且 V1 ,以 V1 为顶点集、两个端点都在 V1 中的 (2) 设 V1 图 G 的边为边集的图 G 的子图，称为 G 的由 V1 导出的子图，记为 G[V1].(3)设 E1 E,且 E1 ,以 E1 为边集,E1 的端点集为顶点集的图 G 的子图, 称为 G 的由 E1 导出的子图,记为 G[E1].
G
G[{v1,v4,v5}]
G[{e1,e2,e3}]
返回
关联矩阵对无向图G,其关联矩阵M=(mij ) ,其中：
1 mij 0
若vi 与e j 相关联 若vi 与e j 不关联
注：假设图为简单图
e1 1 M= 1 0 0
e 2 e3 e 4 e 5 0 0 0 1 v1 1 0 1 0 v2 0 1 1 0 v3 1 1 0 1 v4
对有向图G,其关联矩阵M=(mij ) ,其中：
1 mij 1 0
若vi 是e j的起点 若vi 是e j的终点 若vi 与e j 不关联
返回
邻接矩阵对无向图G,其邻接矩阵 A (aij ) ,其中：
1 aij 0
若vi 与v j 相邻 若vi 与v j 不相邻 A=
注：假设图为简单图v1 v2 v3 v4 0 1 0 1 v1 1 0 1 1 v2 0 1 0 1 v3 1 1 1 0 v4
对有向图G=(V,E) ,其邻接矩阵 A (aij ) ,其中：
1 aij 0
若( vi,v j) E 若( vi,v j) E
对有向赋权图G,其邻接矩阵 A (aij ) ,其中：
wij aij 0
若(vi , v j ) E , 且wij为其权 若i j 若(vi , v j ) E
无向赋权图的邻接矩阵可类似定义.
v1 v2 v3 v4 0 2 7 v1 A= 2 0 8 3 v2 8 0 5 v 3 7 3 5 0 v 4返回
最短路问题及其算法一、 基 本 概 念 二、固 定 起 点 的 最 短 路 三、每 对 顶 点 之 间 的 最 短 路
返回
基 本 概 念定义1 在无向图 G=(V,E, )中： (1) 顶点与边相互交错且 (ei ) v i 1 v i (i=1,2,…k)的有限非空序列
w (v 0 e1 v1 e 2 v k 1 e k v k ) 称为一条从 v0
vk 到
Wv 0 v k 的通路，记为
…… 此处隐藏791字 ……
u1
1
u 67
u2 3
u5 6
u 49
12 u 5