(数学模型 图论 最短路问题
图 论 最短路问题
(数学模型 实验目的 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,Y称为一个图 vn}是有穷非空集,称为顶点集 其中的元素叫图G的顶点 [2]E称为边集,其中的元素叫图G的边 [3]平是从边集E到顶点集V中的有序或无序的元素 偶对的集合的映射,称为关联函数 例1设G=(VE,平),其中 V={v1,v2,v3,v4}, E={el,e2,e3,e中e5}, H(e1)=vV2,H(e2)=vV3,H(e3)=vv4,H(e4)=v1v4,H(e5)=v3 G的图解如图 2 g g 5
定义 有序三元组G=(V,E, ) 称为一个图. [1] V={ , , , } 1 2 n 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 3 3 (e ) = v v ,(e ) = v v ,(e ) = v v ,(e ) = v v ,(e ) = v v . G 的图解如图. 图的定义
(数学模型 定义在图G中,与V中的有序偶(,v对应的边e,称为图的有向 边(或弧),而与V中顶点的无序偶νν,相对应的边e,称为图 的无向边每一条边都是无向边的图,叫无向图;每一条边都是 有向边的图,称为有向图;既有无向边又有有向边的图称为混 图 定义若将图G的每一条边e都对应一个实数w(e),称w(e)为边的权, 并称图G为赋权图 规定用记号v和E分别表示图的顶点数和边数
定义 在图 G 中，与 V 中的有序偶( vi， vj )对应的边 e，称为图的有向 边（或弧），而与 V 中顶点的无序偶 vi vj 相对应的边 e，称为图 的无向边.每一条边都是无向边的图，叫无向图；每一条边都是 有向边的图，称为有向图；既有无向边又有有向边的图称为混 合图. 定义 若将图 G 的每一条边 e 都对应一个实数 w(e)，称 w(e)为边的权， 并称图 G 为赋权图. 规定用记号 和 分别表示图的顶点数和边数