数模图论上课件.pptVIP

二、图的矩阵表示（应用实例及解法分析） 二、图的矩阵表示（应用实例及解法分析） 二、图的矩阵表示（应用实例及解法分析） 二、图的矩阵表示（应用实例及解法分析） 二、图的矩阵表示（应用实例及解法分析） 数学建模-图论 * * 一、图的基本概念 数学建模-图论 * * 一、图的基本概念 一、图的基本概念 次数为奇数顶点称为奇点，否则称为偶点。 * * 数学建模-图论 常用d(v)表示图G中与顶点v关联的边的数目, d(v)称为顶点v的度数. 与顶点v出关联的边的数目称为出度，记作d +(v)， 与顶点v入关联的边的数目称为入度，记作d -(v)。 用N(v)表示图G中所有与顶点v相邻的顶点的集合. 任意两顶点都相邻的简单图称为完全图. 有n个顶点的完全图记为Kn 。 一、图的基本概念 数学建模-图论 几个基本定理： 一、图的基本概念 数学建模-图论 若将图G的每一条边e都对应一个实数F(e), 则称F(e)为该边的权, 并称图G为赋权图, 记为G = (V, E , F ). 设G = (V, E )是一个图, v0, v1, … , vk∈V, 且“1≤i≤k, vi－1 vi∈E, 则称v0 v1 … vk是G的一条通路. 如果通路中没有相同的顶点, 则称此通路为路径, 简称路. 始点和终点相同的路称为圈或回路. 一、图的基本概念 数学建模-图论 顶点u与v称为连通的，如果存在u-v通路，任二顶点都连通的图称为连通图，否则，称为非连通图。极大连通子图称为连通分图。 连通而无圈的图称为树, 常用T 表示树. 树中最长路的边数称为树的高,度为1的顶点称为树叶。其余的顶点称为分枝点。树的边称为树枝。 设G是有向图，如果G的底图是树，则称G是 有向树，也简称树。 一、图的基本概念 数学建模-图论 邻接矩阵（结点与结点的关系） 关联矩阵（结点与边的关系） 路径矩阵（任意两结点之间是否有路径） 可达性矩阵 直达矩阵 等等…… 二、图的矩阵表示 数学建模-图论 1 有向图的邻接矩阵 A = (aij )n×n （n为结点数） 例1：写出右图的邻接矩阵（有向）： 解： 二、图的矩阵表示 数学建模-图论 无向图的邻接矩阵 A = (aij )n×n （n为结点数） 例1：写出右图底图的邻接矩阵： 解： 二、图的矩阵表示 数学建模-图论 性质： 1. 任一无向图的邻接矩阵 A = (aij )n×n 均为对称矩阵。 2. 邻接矩阵A的n次方矩阵的元素代表的意义： A的n次方矩阵中i行j列元素表示从结点i到结点j的长度为n的路径条数。 二、图的矩阵表示 数学建模-图论 2 有向图的权矩阵A = (aij ) n×n （n为结点数） 例2：写出右图的权矩阵： 解： 二、图的矩阵表示 数学建模-图论 3 有向图的关联矩阵A =(aij )n×m （n为结点数m为边数） ? 有向图： 无向图： 二、图的矩阵表示 数学建模-图论 例3：分别写出右边两图的关联矩阵 解：分别为： 二、图的矩阵表示  数学建模-图论 邻接矩阵：节点到节点。关联矩阵：节点到边。 数学建模-图论（坐车） 公交线路选择问题：在给定某城市公交线路的公交网信息后，求任意两个站点之间的最佳出行路线，包括换乘次数最少、出行时间最短、出行费用最低等。以下图的简化公交网为例来说明。 数学建模-图论 1 2 3 4 5 图中由两条公交线路组成，实线表示第一条线路，依次经过站点1,3,4,5，虚线表示第二条线路，依次经过站点2,3,5。 首先考虑换乘次数最少的线路选择模型，首先建立直达矩阵如下： 数学建模-图论 1 2 3 4 5 计算A2得到： 由于A2为非零矩阵，所以任意两站点经过换乘一次都可到达，由于问题较简单，结果显然正确。 一般地，比较A=(aij),A2=(a(2)ij),…, Ak=(a(k)ij)中的(i,j)元够成的向量中第一个非零向量的上标即为出行换乘的最少次数。 数学建模-图论 1 2 3 4 5 接下来考虑出行时间最短的模型，建立直达距离矩阵： 下面利用Floyd矩阵算法可计算出出行时间最短的路线。定义T*T=(t(2)ij), t(2)ij=min{min1=k=5{tik+tkj},tij}, t(2)ij表示从站点i到站点j的至多换乘一次的最短时间。 数学建模-图论 4 1 2 3 5 利用matlab编写程序如下： T=[0 in