关 键 词：

资料 课件 讲义 模型

资源描述：

第二讲 图论模型 1. 问题引入与分析 2. 图论的基本概念 3. 最短路问题及算法 4. 最小生成树及算法 5. 旅行售货员问题 6. 模型建立与求解 回 停 下 1. 问题引入与分析 1) 98年全国大学生数学建模竞赛B题“最佳灾 情巡视路线”中的前两个问题是这样的： 今年(1998年)夏天某县遭受水灾. 为考察灾情、 组织自救，县领导决定，带领有关部门负责人到 全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政 府所在地的路线. 1） 若分三组（路）巡视，试设计总路程最 短且各组尽可能均衡的巡视路线. 2） 假定巡视人员在各乡（镇）停留时间T=2 小时，在各村停留时间t=1小时，汽车行驶速度V =35公里/小时. 要在24小时内完成巡视，至少应分 几组；给出这种分组下最佳的巡视路线. 公路边的数字为该路段的公里数. 2) 问题分析： 本题给出了某县的公路网络图，要求的是在不 同的条件下，灾情巡视的最佳分组方案和路线. 将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次 再回到点O，使得总权（路程或时间）最小. 本题是旅行售货员问题的延伸－多旅行售货员问题. 本题所求的分组巡视的最佳路线，也就是m条 经过同一点并覆盖所有其他顶点又使边权之和达到 最小的闭链（闭迹）. 如第一问是三个旅行售货员问题，第二问是四 个旅行售货员问题. 众所周知，旅行售货员问题属于NP完全问题， 即求解没有多项式时间算法. 显然本问题更应属于NP完全问题. 有鉴于此， 一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大 的问题可使用近似算法来求得近似最优解. 2. 图论的基本概念 1) 图的概念 2) 赋权图与子图 3) 图的矩阵表示 4) 图的顶点度 5) 路和连通 1) 图的概念 定义 一个图G是指一个二元组(V(G),E(G))，其中: 1) V (G) = {v1,v2 ,L,vn }是非空有限集，称为顶点集， 其中元素称为图G的顶点. 2) E(G)是顶点集V(G)中的无序或有序的元素偶对 (vi ,v j ) 组成的集合，即称为边集,其中元素称为边. 定义 图G的阶是指图的顶点数|V(G)|, 用 v 来表示； 图的边的数目|E(G)|用 来表示. G = (V (G), E(G)) 表示图，简记 G = (V , E). 用 viv j (vi ,v j ). 也用 来表示边 例设G = (V (G), E(G)) ， 其中：V (G) = {v1,v2 ,v3,v4}， E(G) = {e1,e2, e3,e4 ,e5,e6} ， e1 = v1v1，e2 = v2v3，e3 = v1v3 e4 = v1v4，e5 = v3v4，e6 = v3v4. （见图 2） 定义 若一个图的顶点集和边集都是有限集，则称 其为有限图. 只有一个顶点的图称为平凡图，其他的 所有图都称为非平凡图. 定义若图G中的边均为有序偶对(vi ,v j ),称G为有向 e = (vi ,v j )是从vi 图. 称边 e = (vi ,v j )为有向边或弧,称 连接 v j ，称 vi为e的尾，称vj为e的头. 若图G中的边均为无序偶对 viv j，称G为无向图.称 边e = viv j 为无向边，称e连接vi 和v j，顶点vi 和vj 称 既有无向边又有有向边的图称为混合图. 为e的端点. 例 设H = (V (H ), E(H ))，其中： V (H ) = {u1,u2 ,u3,u4 ,u5}， E(H ) ={a1, a2, a3, a4 , a5, a6 , a7}， a1 = (u1,u2 ) ， a2 = (u2 ,u2 ) a5 = (u4 ,u3) a3 = (u4 ,u2 ) ， a6 = (u3,u4 ) ， ， ， a4 = (u4 ,u5 ) ， = (u1,u3). （见右图 3） a7 常用术语 1) 边和它的两端点称为互相关联. 2) 与同一条边关联的两个端点称 为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边. 3) 端点重合为一点的边称为环， 端点不相同的边称为连杆. 4) 若一对顶点之间有两条以上的边联结，则这些边 称为重边． 5) 既没有环也没有重边的图，称为简单图． 常用术语 6) 任意两顶点都相邻的简单图,称为完全图. 记为Kv. 7) 若V (G) = X UY，X I Y = f ，且X 中任意两顶点不相邻，Y 中任意两顶点不相邻，则称为二部图或偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为完全二部图或完全偶图,记为Km,n (m=|X|,n=|Y|)． 8) 图 K1,n 叫做星. ， X : x1 x2 x3 X : x1 x2 x3 K1,4 Y : y1 Y : y1 y2 y3 y4 y3 y2 y4 K3,4 二部图 K6 2) 赋权图与子图 定义 若图 G = (V (G), E(G)) 的每一条边e 都赋以一个实数w(e)，称w(e)为边e的权，G 连同边上的权称为赋权图. 定义 设 G = (V , E)和G = (V , E)是两个图. 1) 若V V , E E ,称G是G 的一个子图,记G G. 2) 若V = V，E E ，则称 G是G的生成子图. 3) 若 V V，且 V f，以 V 为顶点集，以两端点 均在V 中的边的全体为边集的图G 的子图，称 G[V ] 为G的由 V 导出的子图，记为 . 4) 若E E，且E f ，以E为边集，以 E 的端点 集为顶点集的图 G 的子图，称为G 的由E 导出的 边导出的子图，记为G[E] . G[{v1,v2 ,v3}] G[{e3,e4 ,e5,e6}] 3) 若 V V，且 V f，以 V 为顶点集，以两端点均在V 中的边的全体为边集的图G 的子图，称 G[V ] 为G的由V 导出的子图，记为 . 4) 若E E，且E f ，以E为边集，以 E 的端点 集为顶点集的图 G 的子图，称为G 的由E 导出的 边导出的子图，记为G[E] . 3) 图的矩阵表示 (以下均假设图为简单图). 邻接矩阵: 1) 对无向图G，其邻接矩阵 A = (aij )n n ，其中： = 1, 若vi与vj相邻, 若vi与vj不相邻. v1 0 a 0, ij v2 1 0 1 0 0 v3 1 1 0 1 1 v4 0 0 1 0 0 v5 0 v1 1 0 v2 A = 1 1 v3 0 0 v 0 4 0 v5 2) 对有向图 G = (V , E) ,其邻接矩阵 A = (aij )n n ,其中： 若(vi ,v j ) E, 若(vi ,v j ) E. = 1, a 0, ij u1 0 0 u2 1 0 1 0 u3 1 0 0 1 u4 1 u1 0 u2 A = 0 u3 0 0 0 u 4 其邻接矩阵 A = (aij )n n 3) 对有向赋权图 G = (V , E) , , 其中： w 若(v ,v ) E,且w 为其权 , ij i j ij = 0， i = j, 若(vi ,v j ) E. aij , u1 0 u2 3 0 6 u3 7 0 4 u4 8 u1 u2 A = u3 0 u 4 对于无向赋权图的邻接矩阵可类似定义. 关联矩阵 1) 对无向图 G = (V , E) 其中： ，其关联矩阵M = (mij )n e 若vi与ej相关联, 若vi与ej不关联. , = 1, m 0, ij e1 1 1 0 0 0 e2 1 0 1 0 0 e3 0 1 1 0 0 e4 0 0 1 1 0 e5 0 v1 M = 0 v2 1 v3 0 v 4 1 v5 2) 对有向图 G = (V , E) ，其关联矩阵 M = (mij )n e , 1, 其中： 若vi是e j的尾, 若vi是e j的头, 若vi不是e j的头与尾. = -1, mij 0, e1 1 -1 e2 0 -1 1 0 e3 1 0 -1 0 e4 1 0 0 -1 e5 0 u1 0 u2 M = -1 u3 0 0 1 u 4 4) 图的顶点度 定义 1) 在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或 dG(v). 称度为奇数的顶点为奇点，度为偶数的顶点为偶点. 2) 在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的度或次数． 定理 d (v) = 2e. vV 推论 任何图中奇点的个数为偶数． d + (u ) = 1 3 d -(u ) = 2 3 d (u3 ) = 3 d (v1) = 4 5) 路和连通 定义1) 无向图G的一条途径（或通道或链）是指 一个有限非空序列 W = v0e1v1e2 Kekvk ，它的项交替 地为顶点和边，使得对 1 i k，ei的端点是vi-1和vi , 称W是从v0 到vk 的一条途径，或一条 (v0 ,vk ) 途径. 整数k称为W的长. 顶点v0 和 vk 分别称为的起点和终点 , 而 v1,v2 ,K,vk -1称为W的内部顶点. 2) 若途径W的边互不相同但顶点可重复，则称W 为迹或简单链. 3) 若途径W的顶点和边均互不相同，则称W为路或路径. 一条起点为v0 ,终点为vk 的路称为 (v0 ,vk ) 路记为P(v0 ,vk ). 定义 1) 途径 W = v0e1v1...ek vk 中由相继项构成子序列 viei+1vi+1...e jv j 称为途径W的节. 2) 起点与终点重合的途径称为闭途径. 3) 起点与终点重合的的路称为圈(或回路)，长为k的圈称为k阶圈，记为Ck. 4) 若在图G中存在(u,v)路，则称顶点u和v在图G 中连通. 5) 若在图G中顶点u和v是连通的，则顶点u和v之之间的距离d(u,v)是指图G中最短(u,v)路的长；若没 没有路连接u和v，则定义为无穷大. 6) 图G中任意两点皆连通的图称为连通图． 7) 对于有向图G，若W = v0e1v1e2 Kekvk ，且 ei 有头 vi 和尾vi-1 ，则称W为有向途径. 类似地，可定义有向迹，有向路和有向圈. 例 在右图中： 途径或链： ugyexeyfxcw 迹或简单链：vbwcxdvaugy路或路径：uavdxcw 圈或回路：uavbwcxfygu 3. 最短路问题及算法 最短路问题是图论应用的基本问题，很多实际问题，如线路的布设、运输安排、运输网络最小费 用流等问题,都可通过建立最短路问题模型来求解. • 最短路的定义 • 最短路问题的两种方法：Dijkstra和Floyd算法 . 1) 求赋权图中从给定点到其余顶点的最短路. 2) 求赋权图中任意两点间的最短路. 定义 1) 若H是赋权图G的一个子图，则称H的各 w(e) 边的权和 w(H ) = 为H的权. 类似地，若 eE(H ) w(e) eE (P) 若P(u,v)是赋权图G中从u到v的路,称 w(P) = 称为路P的权． 2) 在赋权图G中，从顶点u到顶点v的具有最小权的路P*(u,v)，称为u到v的最短路． 3) 把赋权图G中一条路的权称为它的长，把(u,v) 路的最小权称为u和v之间的距离，并记作 d(u,v). 1) 赋权图中从给定点到其余顶点的最短路 最短路是一条路，且最短路的任一节也是最短路． 求下面赋权图中顶点u0到其余顶点的最短路． 假设G为赋权有向图或无向图，G边上的权均非 负．若(u,v) E(G) ，则规定 w(u,v) = +. Dijkstra算法: 求G中从顶点u0到其余顶点的最短路. 1) 置 l(u0 ) = 0，对v u0 ，l(v) = ，S0 = {u0}且 i = 0 . min{l(v),l(ui ) + w(ui ,v)} 2) 对每个 v Si ，用 代替 l(v) ，计算 min{l(v)}，并把达到这个最小值的 vS i 一个顶点记为ui+1，置Si+1 = Si U{ui+1}. 3) 若 i =n -1，则停止；若i 2)更新l(v)、z(v)： l(u) + W (u,v) 则令l(v)=l(u) + W (u,v), z(v)=u 3）设v*是使l(v)取最小值的S 中的顶点，则令 S=S∪{v*}，u v* 4) 若S φ，转 2，否则，停止. 用上述算法求出的l(v)就是u0 到v的最短 路的权，从v的先驱点标记z(v)追溯到u0 , 到u0到v的最短路的路线. 就得 例 求下图从顶点u0到 其余顶点的最短路． 首先写出带权邻接矩阵 3 1 0 3 6 6 4 0 6 4 0 1 0 2 3 7 2 2 0 1 5 7 5 3 0 4 3 4 3 6 0 2 8 1 7 2 W = 7 4 4 2 8 0 因G是无向图，故W 是对称阵． 迭 代 次 数 l(ui ) u0 u1 u2 u 3 u4 u 5 u6 u7 1 2 3 4 5 6 7 8 ０ １ 2 7 4 8 2 4 7 4 8 3 7 4 8 6 9 4 8 6 9 6 9 6 9 最后标记 l(v) z(v) 0 1 2 3 6 9 4 6 u0 u0 u0 u2 u 3 u 3 u0 u6 u1 u2 u0 u4 u u 7 3 u6 u5 见Matlab程序-Dijkstra.doc 2) 求赋权图中任意两顶点间的最短路 • 算法的基本思想 • （I）求距离矩阵的方法. • （II）求路径矩阵的方法. • （III）查找最短路路径的方法. • Floyd算法：求任意两顶点间的最短路. • 举例说明 算法的基本思想 直接在图的带权邻接矩阵中用插入顶点的 方法依次构造出 个矩阵 D(1)、 D(2)、… 、D(n )， 使最后得到的矩阵 D(n )成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路 径． （I）求距离矩阵的方法. 设赋权图G的顶点集为V = {v1,v2 ,K,vn }. 1） 写出赋权图G的带权邻接矩阵W ，把它作为距离矩阵的 初值，即D(0) = (d (0))n n = (wij )n n = W . ij 2）对k = 1,2,K,n ，计算 其中d (k ) = min{d (k -1) , d (k -1) + d (k -1)}, D(k ) = (d (k))n n , ij ij ij ik kj d (k)表示从vi 到v 且中间点仅为v1,v2 ,K,vk 的k 个点的所有 ij j 路径中的最短路的长度。 于是，D(n ) n ) n ) ( ( = (d ) 中元素d 就是从v 到 v 的路径中间可 ij n n ij i j 插入任何顶点的路径中最短路的长度，即D(n )就是所求距离矩阵. （II）求路径矩阵的方法. 在建立距离矩阵的同时可建立路径矩阵R． 设R(k ) = (r(k))n n ，这里r(k)的含义是从vi 到vj 的最短 ij ij 路要经过点号为r(k)的点. ij 算法开始于R(0) = (r(0) )n n ，r(0) = j ， ij ij 若d (k -1) > d (k -1) + d (k -1) , k, ij (k ) ik 否则 kj 迭代到第k 步，rij = (k - 1) r , ij 即由D(k-1)到D(k)迭代，若某个元素改变（变小），则由R(k-1)到 R(k)迭代中，相应元素改为k ，表示到第k 次迭代，从vi 到vj 的最短路过点vk 比过原有中间点更短. 在求得D(n )时求得R(n )，可由R(n )来查找任何点对之间 最短路的路径. （III）查找最短路路径的方法. 若r(n ) = a1，则点va 是点vi 到点v 的最短路的中间点. j ij 1 然后用同样的方法再分头查找．若： (1) 向点vi 追朔得：r(n ) = a2,r(n ) = a3,…,r(n ) = ak . ia1 ia2 iak (2) 向点vj 追朔得：r(n ) = b1,r(n ) = b2,…,r(n ) = j. a1 j b1 j bm j 则由点vi 到vj 的最短路的路径为： vi ,vak ,L,va2 ,va1 ,vb1 ,vb2 ,L,vbm ,v j . vak va3 vi va1 vb1 va2 vb2 v j vbm （IV）Floyd算法：求任意两顶点间的最短路. d(i,j)：i 到 j 的距离． r(i,j)：i 到 j 之间的插入点． 输入: 带权邻接矩阵W = (w(i, j))vv . (1) 赋初值：对所有 i,j, d(i,j)w(i,j), r(i,j)j, k1. (2) 更新 d(i,j), r(i,j): 对所有 i,j，若 d(i,k)+d(k,j)

内容简介：

-