数学建模与数学实验 最短路问题
数学建模与数学实验 最短路问题
实验目的 1.了解最短路的算法及其应用 2.会用 MATLAB软件求最短路 实验内 1.图论的基本概念 2.最短路间题及其算法 3.最短路的应用 4,建模案例:最优截断切割问题 5.实验作业
实验目的 实验内容 2.会用MATLAB软件求最短路 1.了解最短路的算法及其应用 1.图 论 的 基 本 概 念 2.最 短 路 问 题 及 其 算 法 3.最 短 路 的 应 用 4.建模案例:最优截断切割问题 5.实验作业
图论的基本概念 图的概念 1.图的定义 2,顶点的次数 3.子图 二、图的矩阵表示 1.关联矩阵 2,邻接矩阵 返回
图 论 的 基 本 概 念 一、 图 的 概 念 1.图的定义 2.顶点的次数 3.子图 二、 图 的 矩 阵 表 示 1. 关联矩阵 2. 邻接矩阵 返回
国的定义 定义有序三元组G=(VE,平)称为一个图如果: []v={v1,V2…,vn}是有限非空集,V称为顶点集, 其中的元素叫图G的顶点 [2]E称为边集,其中的元素叫图G的边 [3]平是从边集E到顶点集V中的有序或无序的元素 偶对构成集合的映射,称为关联函数 例1设G=(VE,),其中 {v1,v2,v3,v4}, E={e,e2,e3,e4,es}, H(e1)=v2,H(e2)=Vn3,H(e3)=wv4,H(e4)=Vv4,H(e5)=V4v4 G的图解如图 g
定义 有序三元组G=(V,E, ) 称为一个图,如果: [1] V={ , , , } 1 2 n v v v 是有限非空集,V 称为顶点集, 其中的元素叫图 G 的顶点. [2] E 称为边集,其中的元素叫图 G 的边. [3] 是从边集 E 到顶点集 V 中的有序或无序的元素 偶对构成集合的映射,称为关联函数. 例1 设 G=(V,E, ),其中 V={v1 ,v2 , v3 , v4 }, E={e1, e2 , e3, e4, e5 }, 1 1 2 2 1 3 3 1 4 4 1 4 5 4 4 = = = = = ( ) , ( ) , ( ) , ( ) , ( ) e v v e v v e v v e v v e v v . G 的图解如图 图的定义
定义在图G中,与中的有序偶,功对应的边e,称为图的有向边 (或弧),而与V中顶点的无序偶wv相对应的边e,称为图的无 向边每一条边都是无向边的图,叫无向图;每一条边都是有向 边的图,称为有向图;既有无向边又有有向边的图称为混合图 定义若将图G的每一条边e都对应一个实数v(e),则称v(e)为边的 权,并称图G为赋权图 规定用记号v和E分别表示图的顶点数和边数
定义 在图 G 中,与 V 中的有序偶(vi, vj )对应的边 e ,称为图的有向边 (或弧),而与 V 中顶点的无序偶 vi vj 相对应的边e ,称为图的无 向边.每一条边都是无向边的图,叫无向图;每一条边都是有向 边的图,称为有向图;既有无向边又有有向边的图称为混合图. 定义 若将图 G 的每一条边e 都对应一个实数 w( e ),则称 w( e )为边的 权,并称图 G 为赋权图. 规定用记号 和 分别表示图的顶点数和边数
常用术语: (1)端点相同的边称为环 (2)若一对顶点之间有两条以上的边联结,则这些边称为重边 (3)有边联结的两个顶点称为相邻的顶点,有一个公共端点的边 称为相邻的边 (4)边和它的端点称为互相关联的 (5)既没有环也没有平行边的图,称为简单图 (6)任意两顶点都相邻的简单图,称为完备图,记为Kn,其中 为顶点的数目 (7)若VY,X∩Y=Φ,且X中任两顶点不相邻,Y中任两顶 点不相邻,则称G为二元图;若X中每一顶点皆与Y中一切顶点 相邻,则G称为完备二元图,记为Kmn,其中mn分别为X与Y的顶 点数目
常用术语: (1)端点相同的边称为环. (2)若一对顶点之间有两条以上的边联结,则这些边称为重边. (3)有边联结的两个顶点称为相邻的顶点,有一个公共端点的边 称为相邻的边. (4)边和它的端点称为互相关联的. (5)既没有环也没有平行边的图,称为简单图. (6)任意两顶点都相邻的简单图,称为完备图,记为 Kn,其中 n 为顶点的数目. ( 7)若 V=X Y,X Y= ,且 X 中任两顶点不相邻,Y 中任两顶 点不相邻,则称 G 为二元图;若 X 中每一顶点皆与 Y 中一切顶点 相邻,则 G 称为完备二元图,记为 Km,n,其中 m,n 分别为 X 与 Y 的顶 点数目.
返回
返回
顶点的次教 定义(1)在无向图中,与顶点ν关联的边的数目(环算两次)称 为v的次数,记为d(v). (2)在有向图中,从顶点v引出的边的数目称为v的出度, 记为d+(v),从顶点v引入的边的数目称为v的入度,记为d(), d(v)=d+(v)+d(v)称为v的次数 ea al(v4)=2 d(v4)=4 dl(v4)=3 (4)=5
顶点的次数 定义 (1)在无向图中,与顶点 v 关联的边的数目(环算两次)称 为v 的次数,记为d v( ) . (2)在有向图中,从顶点v 引出的边的数目称为v 的出度, 记为d v( ) + ,从顶点v 引入的边的数目称为v 的入度,记为d v( ) - , d v( ) = d v( ) + + d v( ) - 称为 v 的次数. 4 d v( ) 4 = ( ) 5 ( ) 3 ( ) 2 4 4 4 = = = − + d v d v d v
定理1∑d()=26(G) v∈(G) 推论1任何图中奇次顶点的总数必为偶数. 例在一次聚会中,认识奇数个人的人数一定是偶数 返回
定理1 ( ) 2 ( ) ( ) d v G v V G = 推论1 任何图中奇次顶点的总数必为偶数. 例 在一次聚会中,认识奇数个人的人数一定是偶数. 返回
子图 定义设图G=(E,平),G1=(V1E1,平1) (1)若vV,E1CE,且当e∈E1时,Y(e)H(e)则称G1是G的子图 特别的,若V1=V,则G1称为G的生成子图 (2)设VV,且V1≠Φ,以V为顶点集、两个端点都在v1中的 图G的边为边集的图G的子图,称为G的由V导出的子图,记为Gl 3)设E1E,且E1≠Φ,以E1为边集E1的端点集为顶点集的图G的子图 称为G的由E1导出的子图记为G[E 元{v,v4V5 G[{ e.e2.e 返回
子图 定义 设图 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 ]. G G[{v1,v4,v5 }] G[{e1,e2,e3 }] 返回