《数学建模-图论讲稿》由会员分享，可在线阅读，更多相关《数学建模-图论讲稿（86页珍藏版）》请在金锄头文库上搜索。
1、 数学建模图论方法专题图论方法专题一一图的基本概念二二三三最短路问题及其算法四四最小生成树问题五五E图与H图图的矩阵表示数学建模数学建模- -图论图论3*一、图的基本概念数学建模数学建模- -图论图论4*一、图的基本概念一、图的基本概念次数为奇数顶点称为奇点，否则称为偶点。5*数学建模数学建模- -图论图论常用d(v)表示图G中与顶点v关联的边的数目, d(v)称为顶点v的度数. 与顶点v出关联的边的数目称为出度，记作d +(v)， 与顶点v入关联的边的数目称为入度，记作d -(v)。用N(v)表示图G中所有与顶点v相邻的顶点的集合. 任意两顶点都相邻的简单图称为完全图. 有n个顶点的完全图记
2、为Kn 。一、图的基本概念数学建模数学建模- -图论图论几个基本定理：一、图的基本概念数学建模数学建模- -图论图论若将图G的每一条边e都对应一个实数F(e), 则称F(e) 为该边的权, 并称图G为赋权图, 记为G = (V, E , F ). 设G = (V, E )是一个图, v0, v1, , vkV, 且 “1ik, vi1 viE, 则称v0 v1 vk是G的一条通路.如果通路中没有相同的顶点, 则称此通路为路径, 简称 路. 始点和终点相同的路称为圈或回路. 一、图的基本概念数学建模数学建模- -图论图论顶点u与v称为连通的，如果存在u到v通路，任二顶 点都连通的图称为连通图，否
3、则，称为非连通图。极大 连通子图称为连通分图。连通而无圈的图称为树, 常用T 表示树. 树中最长路的边数称为树的高，度数为1的顶点 称为树叶。其余的顶点称为分枝点。树的边称为树 枝。设G是有向图，如果G的底图是树，则称G是 有向树，也简称树。一、图的基本概念数学建模数学建模- -图论图论邻接矩阵（结点与结点的关系） 关联矩阵（结点与边的关系） 路径矩阵（任意两结点之间是否有路径） 可达性矩阵 直达矩阵等等二、图的矩阵表示数学建模数学建模- -图论图论1 有向图的邻接矩阵 A = (aij )nn （n为结点数）例1：写出右图的邻接矩阵：解：二、图的矩阵表示数学建模数学建模- -图论图论2 有向
4、图的权矩阵A = (aij ) nn （n为结点数） 例2：写出右图的权矩阵：解：二、图的矩阵表示数学建模数学建模- -图论图论3 有向图的关联矩阵A =(aij )nm （n为结点数m为边数） 有向图： 无向图：二、图的矩阵表示数学建模数学建模- -图论图论例3：分别写出右边两图的关联矩阵解：分别为：二、图的矩阵表示数学建模数学建模- -图论图论二、图的矩阵表示4 应用实例某厂生产一种弹子锁具，每个锁具的钥匙有5个槽 ，每个槽的高度从1，2，3，4，5，6)中任取一数 由于工艺及其它原因，制造锁具时对5个槽的高度有两 个限制： (1)至少有3个不同的数； (2)相邻两槽的高度之差不能为5满足
5、以上条件制造出来的所有互不相同的锁具称 为一批我们的问题是如何确定每一批锁具的个数?1994年全国大学生数学建模竞赛B题(锁具装箱)中关于 锁具总数的问题可叙述如下：数学建模数学建模- -图论图论该问题用图论中的邻接矩阵解决较为简单 易见， x=t-s，其中，t代表相邻两槽高度之差不为5 的锁具数，即：满足限制条件(2)的锁具数，s代表相 邻两槽高度之差不为5且槽高仅有1个或2个的锁具数， 即：满足限制条件(2)但不满足限制条件(1)的锁具数 我们用图论方法计算t和s.数学建模数学建模- -图论图论二、图的矩阵表示（应用实例及解法分析）在G中t每一条长度为4的道路对应于一个相邻两槽 高度之差不
6、超过5的锁具，即满足限制条件（2）的锁 具，反之亦然，于是可以通过G的邻接矩阵A来计算t的 值，具体步骤如下：数学建模数学建模- -图论图论二、图的矩阵表示（应用实例及解法分析）构造无向图 124356因此， 数学建模数学建模- -图论图论二、图的矩阵表示（应用实例及解法分析）又令 其中yi表示满足限制条件(2)但不满足限制条件(1)且 首位为i的锁具数,（i=1,2,3,4,5,6),显然y1=y6, y2=y4=y3=y5,于是我们只需要计算y1和y2.计算y1可分别考虑槽高只有1，12，13，14，15的 情形若只有1，这样的锁具效只有1个， 若只有1和i(i=2,3,4,5)，这样的锁
7、具数=G中以1和i为 顶点，长度为3的道路数，此数可通过A的子矩阵A1i计 算得到数学建模数学建模- -图论图论二、图的矩阵表示（应用实例及解法分析）124356二、图的矩阵表示（应用实例解法分析）事实上，因为 其中i=2,3,4,5,显然y1=1+(4+4+4+4-1) 4=61.同理，计算y2时应考虑槽高只有2,21,23,24,25, 26时的情形，类似计算可得y2=1+(4+4+4+4-1)5=76于是，s=612+764=426，x=6306-426=5880.该算法既易理解又易操作并且又可扩展数学建模数学建模- -图论图论二、图的矩阵表示（应用实例及解法分析）公交线路选择问题：在给
8、定某城市公交线路的公交网信息后 ，求任意两个站点之间的最佳出行路线，包括换乘次数最少、出 行时间最短、出行费用最低等。以下图的简化公交网为例来说明 。 数学建模数学建模- -图论图论12345图中由两条公交线路组成，实线表示第 一条线路，依次经过站点1,3,4,5，虚线表 示第二条线路，依次经过站点2,3,5。首先考虑换乘次数最少的线路选择模型，首 先建立直达矩阵如下：二、图的矩阵表示（应用实例及解法分析）数学建模数学建模- -图论图论12345计算A2得到 ：由于A2为非零矩阵，所以任意两站点经 过换乘一次都可到达，由于问题较简单，结 果显然正确。一般地，比较A=(aij),A2=(a(2)
9、ij), Ak=(a(k)ij)中的(i,j)元够成的向量中第一个 非零向量的上标即为出行换乘的最少次数。二、图的矩阵表示（应用实例及解法分析）数学建模数学建模- -图论图论12345接下来考虑出行时间最短的 模型，建立直达距离矩阵：下面利用Floyd矩阵算法可计算出出行时 间最短的路线。定义T*T=(t(2)ij), t(2)ij=minmin1，如右 图所示。G=的邻接矩阵为：二、图的矩阵表示（应用实例及解法分析）数学建模数学建模- -图论图论V10 v11 v12 v13 v14 v15 v16 v17 v18v1 v2 v3 v4 v5 v6 v7 v8 v9其中，矩阵B为 ：记a(k
10、)ij为Ak中的（i,j）元，目标是使a(k)1,10不等于0的最小的 自然数k.利用matlab容易计算出k=11，且a(11)1,10 =4,即小船至少11次才 能把所有人全部运到右岸，说明共有4种不同的过河方案。继续计 算可得出a(19)1,10 =45060，如果允许小船过河19次的话，共有 45060中不同的方案。若将图G的每一条边e都对应一个实数F(e), 则称F(e) 为该边的权, 并称图G为赋权图, 记为G = (V, E , F ). 设G = (V, E )是一个图, v0, v1, , vkV, 且 “1ik, vi1 viE, 则称v0 v1 vk是G的一条通路. 如果
11、通路中没有相同的顶点, 则称此通路为路径,简称路.对于赋权图，路的长度（即路的权）通常指路上所有边 的权之和。最短路问题：求赋权图上指定点之间的权最小的路。 三、最短路问题及其算法数学建模数学建模- -图论图论重要性质：若v0 v1 vm 是G 中从v0到vm的最短路, 则 对1km, v0v1 vk 必为G 中从v0到vk的 最短路. 即：最短路是一条路，且最短路的任一段 也是最短路。数学建模数学建模- -图论图论三、最短路问题及其算法设有给定连接若干城市的公路网，寻求从指定城 市到各城市的最短路线。2、应用实例：最短路问题问题的数学模型: 三、最短路问题及其算法31*数学建模数学建模- -
12、图论图论32*三、最短路问题及其算法数学建模数学建模- -图论图论25464710913710664833*三、最短路问题及其算法数学建模数学建模- -图论图论34*三、最短路问题及其算法数学建模数学建模- -图论图论35*三、最短路问题及其算法数学建模数学建模- -图论图论36*三、最短路问题及其算法数学建模数学建模- -图论图论25464710913710664837*三、最短路问题及其算法数学建模数学建模- -图论图论38*三、最短路问题及其算法数学建模数学建模- -图论图论39*三、最短路问题及其算法数学建模数学建模- -图论图论40*三、最短路问题及其算法数学建模数学建模- -图论图
13、论25464710913710664841*三、最短路问题及其算法数学建模数学建模- -图论图论42*三、最短路问题及其算法数学建模数学建模- -图论图论43*三、最短路问题及其算法数学建模数学建模- -图论图论25464710913710664844*三、最短路问题及其算法数学建模数学建模- -图论图论45*数学建模数学建模- -图论图论三、最短路问题及其算法46*数学建模数学建模- -图论图论求v1到v6的最短路问题. 三、最短路问题及其算法47*数学建模数学建模- -图论图论从上图中容易得到v1到v6只有两条路： v1v3v6和v1v4v6. 而这两条路都是v1到v6的最短路.三、最短路
14、问题及其算法48*三、最短路问题及其算法数学建模数学建模- -图论图论顶点u与v称为连通的，如果存在u-v通路，任二顶点 都连通的图称为连通图，否则，称为不连通图。极大连 通子图称为连通分图。连通而无圈的图称为树, 常用T 表示树. 树中最长路的边数称为树的高的度为1的顶点称 为树叶。其余的顶点称为分枝点。树的边称为树枝 。设G是有向图，如果G的底图是树，则称G是 有向树，也简称树。四、最小生成树问题及其算法数学建模数学建模- -图论图论若任意一个连通的图G=的生成子图 T=(V=V,E为E的子集)为树, 这棵树T 称为图G的生成树. 设T是图G的一棵生成树, 用F (T)表示树T中所有边 的
15、权数之和, F(T)称为树T的权.一个连通图G的生成树一般不止一棵, 图 G的所有生成树中权数最小的生成树称为 图G的最小生成树.数学建模数学建模- -图论图论四、最小生成树问题及其算法怎样找出最小生成树？G T1 T2 T3 T4 T5 T6 T7 T8 T1至T8是 图G的生 成树数学建模数学建模- -图论图论四、最小生成树问题及其算法Kruskal 算法 思想：在不形成圈得条件下，优先挑选权小的边形成生成 树。7678833 4245v1v2v3v4v5v6v7 683324v1v2v3v4v5v6v7数学建模数学建模- -图论图论四、最小生成树问题及其算法注：算法构造的最小生成树的边集为 E1；标号 l 具有性质 ：当且仅当 u、v 之间有一条仅由 E1 中的边形成的路时， l(u) = l(v)，因此在步骤 (2) 发现 l(u) =
