资源描述：
《第8讲 最短路问题new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数学建模与数学实验最短路问题实验目的1．了解最短路的算法及其应用2．会用MATLAB软件求最短路实验内容1．图论的基本概念2．最短路问题及其算法3．最短路的应用4．建模案例：最优截断切割问题5．实验作业图论的基本概念一、图的概念1．图的定义2．顶点的次数3．子图二、图的矩阵表示1．关联矩阵2．邻接矩阵返回图的定义定义有序三元组G=(V,E,)Ψ称为一个图,如果：[1]V={v,v,?,v}是有限非空集，V称为顶点集，12n其中的元素叫图G的顶点.[2]E称为边集，其中的元素叫图G的边.[3]Ψ是从边集E到顶点集V中的有序或无
2、序的元素偶对构成集合的映射，称为关联函数.例1设G=(V,E,Ψ)，其中V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5},Ψ=Ψ=Ψ=Ψ=Ψ=()evvev,()vev,()vev,()vev,()v.112213314414544G的图解如图定义在图G中，与V中的有序偶(vi，vj)对应的边e，称为图的有向边（或弧），而与V中顶点的无序偶vivj相对应的边e，称为图的无向边.每一条边都是无向边的图，叫无向图；每一条边都是有向边的图，称为有向图；既有无向边又有有向边的图称为混合图.定义若将图G的每一条边e
3、都对应一个实数w(e)，则称w(e)为边的权，并称图G为赋权图.规定用记号ν和ε分别表示图的顶点数和边数.常用术语：（１）端点相同的边称为环．（２）若一对顶点之间有两条以上的边联结，则这些边称为重边．（３）有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边．（４）边和它的端点称为互相关联的．（５）既没有环也没有平行边的图，称为简单图．（６）任意两顶点都相邻的简单图，称为完备图，记为Kn，其中n为顶点的数目．(7)若V=X∪Y，X∩Y=Φ，且X中任两顶点不相邻，Y中任两顶点不相邻，则称G为二元图；若X中每一顶点皆
4、与Y中一切顶点相邻，则G称为完备二元图，记为Km,n，其中m,n分别为X与Y的顶点数目．返回顶点的次数定义（１）在无向图中，与顶点v关联的边的数目（环算两次）称为v的次数，记为dv()．（２）在有向图中，从顶点v引出的边的数目称为v的出度，＋－记为dv()，从顶点v引入的边的数目称为v的入度，记为dv()，dv()＋－=dv()+dv()称为v的次数．+d(v)=24dv()44=−d(v)=34d(v)=54定理１∑d(v)=2ε(G)v∈V(G)推论１ 任何图中奇次顶点的总数必为偶数．例在一次聚会中，认识奇数个人的人数一
5、定是偶数.返回子图定义设图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].GG[{v1,v4,v5}]G[{e1,e2,e3}]返回关联矩阵对无向
6、图Ｇ，其关联矩阵Ｍ＝(m)，其中：ijν×ε⎧1若与相关联veijm=⎨注：假设图为简单图ij0若与不关联ve⎩ijeeeee12345⎛10001⎞v1⎜⎟M=⎜11010⎟v2⎜⎟00110v⎜⎟3⎜⎟⎝01101⎠v4对有向图Ｇ，其关联矩阵Ｍ＝(m)，其中：ijν×ε⎧1若v是e的起点ij⎪mij=⎨−1若vi是ej的终点⎪0若v与e不关联⎩ij返回邻接矩阵对无向图Ｇ，其邻接矩阵A=(a)，其中：ijν×ν⎧1若vi与vj相邻aij=⎨0注：假设图为简单图⎩若vi与vj不相邻vvvv1234⎛0101⎞v1⎜⎟A=⎜1
7、011⎟v2⎜⎟0101v⎜⎟3⎜⎟⎝1110⎠v4对有向图Ｇ＝（Ｖ，Ｅ），其邻接矩阵A=(a)，其中：ijν×ν⎧1若（vi，vj）∈Eaij=⎨0⎩若（vi，vj）∉E对有向赋权图Ｇ，其邻接矩阵A=(a)，其中：ijν×ν⎛w若(v,v)∈E,且w为其权ijijij⎜a=0若i=jij⎜⎜∞若(v,v)∉E⎝ij无向赋权图的邻接矩阵可类似定义．vvvv1234⎛02∞7⎞v1⎜⎟A=⎜2083⎟v2⎜⎟∞805v⎜⎟3⎜⎟⎝7350⎠v4返回最短路问题及其算法一、基本概念二、固定起点的最短路三、每对顶点之间的最短路返回基
8、本概念定义１在无向图G=(V,E,Ψ)中：（１）顶点与边相互交错且Ψ(e)=vv(i=1,2,…,k)的有限非空序列ii−1iw=(veve?vev)称为一条从v到v的通路，记为W0112k−1kk0kv0vk（２）边不重复但顶点可重复的通路称为道路，记为Tv0vk（３）边与顶点均不重复的
