第八章 最短路问题 -

第八章 最短路问题

实验目的

1、了解最短路的算法及其应用

2、会用Matlab软件求最短路 实验内容 一、图论的基本概念 1、 图的概念 图的定义

定义 有序三元组G=(V,E,?)称为一个图. [1]

V={v1,v2,?,vn}是有穷非空集，称为顶点集，其中的元素叫图G的顶点. [2] E称为边集，其中的元素叫图G的边.

?是从边集E到顶点集V中的有序或无序的元素偶对的集合的映射，称[3]

为关联函数.

例1 设G=(V,E,?)，其中 V={v1 ,v2 , v3 , v4}， E={e1, e2 , e3, e4, e5},

?(e1)?v1v2,?(e2)?v1v3,?(e3)?v1v4,?(e4)?v1v4,?(e5)?v3v3.

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的顶点数目．

GG[{v1,v4,v5}]G[{e1,e2,e3}]

2、顶点的次数

定义 (1)在无向图中，与顶点v关联的边的数目（环算两次）称为v的次数，记为d(v)． (2)在有向图中，从顶点v引出的边的数目称为v的出度， 记为d+(v)，从顶点v引入的边的数目称为的入度，记为d-(v)， d(v)=d+(v)+d-(v)称为v的次数．

d?(v4)?2d?(v4)?3d(v4)?5

d(v4)?4

定理１

v?V(G)?d(v)?2?(G)

推论１ 任何图中奇次顶点的总数必为偶数．

例 在一次聚会中，认识奇数个人的人数一定是偶数。 3、子图

定义 设图G=(V,E,?),G1=(V1,E1,?1)

(1)若V1?V，E1?E,且当e?E1时，?1(e)= ?(e),则称G1是G的子图．特别的，若V1=V，则G1称为G的生成子图．

(2)设V1?V，且V1??，以V1为顶点集、两个端点都在V1中的图G的边为边集的图G的子图，称为G的由V1导出的子图，记为G[V1].

(3)设E1?E,且E1??,以E1为边集,E1的端点集为顶点集的图G的子图,称为G的由E1导出的子图,记为G[E1].

图的矩阵表示 1、关联矩阵

对无向图Ｇ，其关联矩阵Ｍ＝(mij)???，其中：

1mij???0?若vi与ej相关联 注：假设图为简单图

若vi与ej不关联e2e3e4e50001?v1?1010?v2 0110?v3?1101??v4e1?1? M=?1?0??0?对有向图Ｇ，其关联矩阵Ｍ＝(mij)???，其中：

?1?mij???1?0?若vi是ej的起点若vi是ej的终点 若vi与ej不关联2、邻接矩阵

对无向图Ｇ，其邻接矩阵A?(aij)???，其中：

1aij???0?若vi与vj相邻 注：假设图为简单图

若vi与vj不相邻v4?v1??v2 ?v?3?v?4v1v2v3?0101? A=?1011?0101??1110?对有向图Ｇ＝（Ｖ，Ｅ），其邻接矩阵A?(aij)???，其中：

1aij???0?若（vi，vj）?E

若（vi，vj）?E对有向赋权图Ｇ，其邻接矩阵A?(aij)???，其中：

?wij?aij??0???若(vi,vj)?E,且wij为其权 若i?j若(vi,vj)?E无向赋权图的邻接矩阵可类似定义．

v1v2?02? A=?20??8??73?

二、最短路问题及其算法

三、最短路的应用

四、建模案例：最优截断切割问题 五、实验作业

v3v4?7?v1?83?v2 05?v3?50??v4

本文来源：https://www.bwwdw.com/article/jt82.html