第6讲 图论模型 图论模型中包含的内容很多，我们重点介绍两种建模中用的最广泛的图论算法。

Presentation on theme: "第6讲 图论模型 图论模型中包含的内容很多，我们重点介绍两种建模中用的最广泛的图论算法。"— Presentation transcript:

1 第6讲 图论模型 图论模型中包含的内容很多，我们重点介绍两种建模中用的最广泛的图论算法。

2 【主要内容】 介绍图的基本概念，重点介绍图论模型中的最短路算法及最小生成树算法。
数学建模 数学建模 第6讲 图论模型 【主要内容】 介绍图的基本概念，重点介绍图论模型中的最短路算法及最小生成树算法。 【主要目的】了解基本图论模型的算法及其在数学建模中的应用。 我们这里重点关注图的顶点之间的关系，如距离，如连接关系，下次课我们将来关注边的限制以及对顶点和边的关系。

3 C A B D 第6讲 图论模型 目前普遍认为图论最早的研究是从1763年著名数学家欧拉研究哥尼斯堡七桥环游问题开始。 哥尼斯堡七桥问题
第6讲 图论模型 目前普遍认为图论最早的研究是从1763年著名数学家欧拉研究哥尼斯堡七桥环游问题开始。 A B C D 哥尼斯堡七桥问题：哥尼斯堡城内有一条河（普雷格尔河），中间有2个岛，在岛与陆地以及岛与岛之间有7座桥，哥尼斯堡居民乐意玩这样一个游戏…相关的问题还有中国邮递员问题（走遍所有的街道，可以不止一次) 环球旅行问题：12面体，从一个顶点出发走遍所有顶点仅一次回到这里。 演化为旅行商问题（推销员需要拜访多个地点） 四色问题：任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。 图论问题具有悠久的历史，在数学建模中图论问题也是一类重要的问题。下面我们先来看看关于图的一些基本概念 哥尼斯堡七桥问题 哈密尔顿环球旅行问题 四色问题

4 图的基本概念 第6讲 图论模型 定义 一个图G是指一个二元组(V(G),E(G))，其中: 是非空有限集，称为顶点集， 1)
第6讲 图论模型 图的基本概念 定义 一个图G是指一个二元组(V(G),E(G))，其中: 是非空有限集，称为顶点集， 1) 其中元素称为图G的顶点. 2) E(G)是顶点集V(G)中的元素偶对 组成的集合，称为边集,其中元素称为边. 图描述顶点以及不同顶点之间的关系，也就是用边来描述 用 来表示边 表示图，简记 一般用

5 基本概念 第6讲 图论模型 （1）无（有）向图 （2）相邻顶点（边） （3）路、环（圈） （4）权（赋权图） （5） 阶、入度、出度
第6讲 图论模型 基本概念 （1）无（有）向图 （2）相邻顶点（边） （3）路、环（圈） （4）权（赋权图） （5） 阶、入度、出度 （6）连通图、子图 （7）树 （8）完全图、二部图 完全图 二部图 路：从起点出发经过一系列中间顶点到达终点，就叫做一条路 环：起点和终点重合，且中间没有其它顶点 圈：起点和终点重合，但中间还具有其它顶点 权：给边赋的一个值。其一般反应的是顶点之间的关系或边上的约束，如费用、代价等等 入度（出度）：针对赋权图而言 连通图：任意两点之间存在路（可达） 子图：有两种，一种是点和边都是原图的一部分（边导出子图，点导出子图），另外一种是点是原图的所有点，边是一部分，称为支撑子图。 树：简单的讲就是连通的无圈图 完全图：任意两个顶点之间均有边连接的没有环和重边的图 二部图：二分图，顶点能分成两部分，每部分顶点内部没有边相连，而边都在两部分顶点之间

6 第6讲 图论模型 图的矩阵表示 （1）邻接矩阵：建立顶点之间的关系 （2）关联矩阵：建立顶点与边之间关系 思考：A﹒A中元素的物理含义

7 （1）最短路：钢管订购与运输(00B)，乘公交看奥运(07B)，打孔机生产效能的提高(12夏令营）;
数学建模中较常见的图论问题 （1）最短路：钢管订购与运输(00B)，乘公交看奥运(07B)，打孔机生产效能的提高(12夏令营）; （2）最小生成树：通讯网络最优连接（91MCMB）,灾情巡视（98B）； （3）二部图最大匹配（最大独立顶点集）：招聘（面试）问题，排课问题，锁具装箱（94B）; （4）最大完全子图：钻井布局（99B）; （5）旅行商问题：碎纸片拼接复原问题（13B）

8 第6讲 图论模型 最短路问题及其算法 设P(u, v) 是赋权图G = (V, E , F) 中从点u到v的路径, 用E(P) 表示路径P(u, v)中全部边的集合, 记 则称F (P)为路径P(u, v) 的权或长度(距离)。 定义 若P0 (u, v) 是G 中连接u, v的路径, 且对任意在G 中连接u, v的路径P (u, v)都有 F (P0)≤F(P), 则称P0 (u, v) 是G 中连接u, v的最短路。

9 设P(v0,vm)为图中从v0到vm的最短路，其经过的顶点为
第6讲 图论模型 设P(v0,vm)为图中从v0到vm的最短路，其经过的顶点为 (v0,v1,v2,…vk), 则对于任意0<k<m， (v0,v1,v2,…vk)必为从v0到vk的最短路。 最短路中任意一段从起点出发的路径也是最短路！ 求解非负赋权图最短路算法有两种： （1）指定两点之间最短路-Dijkstra算法 （2）图中任意两点之间的最短路-Floyd算法 最短路性质 狄杰斯特拉算法 佛洛伊德算法

10 第6讲 图论模型 Dijkstra算法(标号法） 基本思想：从起点 S 沿一切 可能的弧派遣使者，这些使 者均以相同的速度匀速前进
第6讲 图论模型 Dijkstra算法(标号法） 基本思想：从起点 S 沿一切 可能的弧派遣使者，这些使 者均以相同的速度匀速前进 ，最早有使者到达的顶点作 上记号，记下历经的路的长度，然后从这点沿所有可能的弧再派出使者，这些使者与原来尚未到达顶点的使者一起以相同速度匀速前进，…，重复以上过程，直到有人到达终点为止。 也就是说，不断的比较当前已经达到的点的路径长度，而其中最小路径的点一定是已经寻找到了从起点到达该点的最短路

11 T ( j )——第 j 个点的临时标号，当前已走过道路的最短路； P( j )——第 j 个点的永久标号，记录最短路长。
第6讲 图论模型 算法步骤： 设弧不可达时的长度为∞。 T ( j )——第 j 个点的临时标号，当前已走过道路的最短路； P( j )——第 j 个点的永久标号，记录最短路长。 Step 1 令 P(1)=T(1)=0, T( j )=∞, j = 2,3, …,N. Step 2 计算 T( j ) = min {T( j ) , P(1)+d1j }, j = 2,3, …,N. 如果结点 j 的临时标号发生了变化，就令 PRIOR( j ) = 1 . 临时编号T(j)：当前找到的最短路 永久编号：从起点到达该点的最短路 Prior(j)记录最短路的前一个顶点

12 第6讲 图论模型 Step 3 取出所有临时标号中最小的一个标号（若多个，任 取其一），改为永久性标号，即若 k 是临时标号最小
第6讲 图论模型 Step 3 取出所有临时标号中最小的一个标号（若多个，任 取其一），改为永久性标号，即若 k 是临时标号最小 的一个结点，则令 P( k )=T( k ). 若无临时标号点或 k = N，则转Step 5；否则，转Step 4. Step 4 设刚获得永久性标号的点为 k ，对每个具有临时 标号的点 j ，计算 T( j ) = min {T( j ) , P(k)+dkj } 对于T( j )发生了变化的每个结点 j ，令PRIOR( j ) = k , 然后转Step 3. 找临时编号中最小标号是最关键的一个步骤：因为它一定是到达该点的最短路了 Step4： 一旦出现了一个永久标号，也就是找到了一个点的最短路径，则它有可能影响到与它相关的点的路径长度，所以需要更改 这两个步骤是最短路算法的核心

13 第6讲 图论模型 ∞ （1）T(S)=0, T(j) = ∞, j = 2,3, …,6 Step 5 P(N) 即为1→N的最短路的长。
第6讲 图论模型 Step 5 P(N) 即为1→N的最短路的长。 设 PRIOR( ki ) = ki-1 , i=1,2, …,n; k0 = 1 , kn = N, 则最短路径为：1 = k0 → k1 → k2 → … → kn = N. 以下图为例说明最短路求解的过程。 ∞ （1）T(S)=0, T(j) = ∞, j = 2,3, …,6

14 第6讲 图论模型 5 ∞ 3 （2）T(B1)=min{∞,T(S)+5}=5 T(B2)=min{∞,T(S)+3}=3 PRIOR( B2) = S

15 第6讲 图论模型 5 ∞ 3 10 11 9 （3）T(C2)=min{∞,T(B2)+8}=11 T(C3)=min{∞,T(B2)+7}=10 T(C4)=min{∞,T(B2)+6}=9 PRIOR( B1) = S

16 第6讲 图论模型 6 ∞ 5 8(11) 10 3 9 （4）T(C1)=min{∞,T(B1)+1}=6
第6讲 图论模型 5 6 3 10 8(11) 9 ∞ （4）T(C1)=min{∞,T(B1)+1}=6 T(C2)=min{11,T(B1)+3}=8 T(C3)=min{10,T(B1)+6}=10 这就告诉我们，所有临时编号中最小的一定是没有问题的，但不是最小的路径则有可能还会改变 PRIOR( C1) = B1

17 第6讲 图论模型 5 6 3 10 8 9 12 14 ∞ （5） T(D1)=min{∞,T(C1)+6}=12 T(D2)=min{∞,T(C1)+8}=14 PRIOR( C2) = B1

18 第6讲 图论模型 5 6 3 10 8 9 11(12) 13(14) ∞ （6） T(D1)=min{12,T(C2)+3}=11 T(D2)=min{14,T(C2)+5}=13 PRIOR( C4) = B2

19 第6讲 图论模型 5 6 3 10 8 9 11 13 ∞ （7） T(D2)=min{13,T(C4)+8}=13 T(D3)=min{∞,T(C4)+4}=13 PRIOR( C3) = B2

20 第6讲 图论模型 5 6 3 10 8 9 11 13 ∞ （8） T(D2)=min{13,T(C3)+3}=13 T(D3)=min{13,T(C3)+3}=13 PRIOR( D1) = C2

21 第6讲 图论模型 5 6 3 10 8 9 11 13 14 （9） T(E)=min{∞,T(D1)+3}=14 PRIOR( D2) = C3

22 第6讲 图论模型 5 6 3 10 8 9 11 13 14 最短路：S->B1->C2->D1->E Dijkstra算法可以得到起点到所有点之间的最短路

23 第6讲 图论模型 Dijkstra算法适用于： （1）起点和终点已知的最短路问题； （2）起点或终点已知的最短路算法； Floyd算法：求图中任意两点之间最短路。 笛杰斯特拉算法

24 模型的转化是图论算法应用的关键！ 第6讲 图论模型 设某公司需使用某种设备一套，设备购买价格及维修费用见表。
第6讲 图论模型 模型的转化是图论算法应用的关键！ 例 1（设备更新问题） 设某公司需使用某种设备一套，设备购买价格及维修费用见表。 现设该公司在第一年开始时新购入一套设备，问今后 5 年的设备更新方案如何，才能使得总费用最省？ 年 1 2 3 4 5 价格 11 12 13 使用 年限 0－1 1－2 2－3 3－4 4－5 维修费用 5 6 8 11 18 粗看起来是优化问题， 目的就是在这5年中寻找设备的购买点，那么穷举所有方案格式为2^5

25 第6讲 图论模型 建立图论模型 结点i 表示第i 年开始时 购买一套设备，结点6为虚 设结点。 用pi表示第i 年的购买费，
第6讲 图论模型 建立图论模型 结点i 表示第i 年开始时 购买一套设备，结点6为虚 设结点。 用pi表示第i 年的购买费， mk表示k个使用年限的维修费。 弧( i, j )的长度dij 为第i年的购买费与 j - i 年里的维修费之和，即 求①→⑥的最短路. Dij:第i年购买设备，然后第j年更新再次购买

26 第6讲 图论模型 例 2（渡河问题） 农夫带着狼、羊和白菜过河，因为船比较小，每次只能带一样东西过河。并且狼和羊，羊和白菜都不能在无人看管的情况下留在一起。否则狼会吃羊，羊会吃白菜。问如何安全、快速的过河？ 考虑原岸边的情况。人、狼、羊、菜共有 = 16种组合 ，“狼羊菜”、“羊菜”、“狼羊”三种状态不能出现，所以与之相对应的“人”、“人狼”、“人菜”这三种状态也不会出现。剩下10 种情况：“人狼羊菜”、“人狼羊”、“人狼菜”、“人羊菜”、“人羊”、“狼菜”、狼、羊、菜、空。

27 第6讲 图论模型 寻找一条从“人狼羊菜”状态到空状态的最短路

28 第6讲 图论模型 图论的很多问题本质上也是优化问题，如最短路问题就可以用建立规划模型来解决。 假设有向图有n个顶点，现需要求从顶点1到顶点n的最短路.设图中(i,j)边上的权重为wij，设决策变量为xij=1说明弧(i,j)位于顶点1至顶点n 的路上；则线性规划模型可表达为 构成从起点1到终点n的一条路

29 第6讲 图论模型 最短路的线性规划模型 建立图的赋权矩阵wij和邻接矩阵pij S B1 B2 C1 C2 C3 C4 D1 D2 D3 E
第6讲 图论模型 最短路的线性规划模型 S B1 B2 C1 C2 C3 C4 D1 D2 D3 E 5 3 1 6 8 7 4 2 S B1 B2 C1 C2 C3 C4 D1 D2 D3 E 1 建立图的赋权矩阵wij和邻接矩阵pij

30 第6讲 图论模型 最短路的线性规划模型 求解模型可得 X(S,B1)=1 X(B1,C2)=1 X(C2,D1)=1 X(D1,E)=1 最短路：S->B1->C2->D1->E

31 最小生成树问题及其算法 第6讲 图论模型 树：无回路的连通图。树具有如下 （1）边数等于顶点数减1；
第6讲 图论模型 最小生成树问题及其算法 树：无回路的连通图。树具有如下 （1）边数等于顶点数减1； （2）树中任意两个顶点之间恰有一条通路； （3）树中任意去掉一条边，则得到一个不连通图； （4）树中任意两个顶点之间添加一条新边，恰有一条回路。 对于图G的支撑子图（顶点集不变，边取子集）若是树，则称为生成树。 赋权图中所有权加起来最小的树称为最小生成树

32 最小生成树-Kruskal算法 第6讲 图论模型
第6讲 图论模型 最小生成树-Kruskal算法 构造思想：对一个连通赋权图G，选择所有结点构成最小生成树的顶点，将图G的所有边按权从小到大进行排序，依次选择边连接顶点，若加入的边构成圈，则不选择，继续这种做法直到产生生成树。 算法步骤： （1）将G的m条边e1,e2,…,em按权的递增顺序排成序列 即 取：设当前边集和顶点编号分别为: 为了验证是否产生回路，对每个点做个编号

33 第6讲 图论模型 （2）对于k=1,2…,m依次判断边eik的两个端点u,v的标号是否相等，若相等，则k=k+1,转(2)，否则，取 （3）对所有满足标号l(vj)=max{l(u),l(v)}中的vj取l(vj)=min{l(u),l(v)}，主要目的是保持当前已入选边顶点具有相同编号 （4）若E中边个数为n-1，否则取k=k+1，转(2) 可证明：用Kruskal算法一定可求得最小生成树。

34 第6讲 图论模型 案例 ：通讯网络最佳连接（91MCMB） 某通讯公司在县城设有九个通讯站，他们的位置可以用平面直角坐标系下的坐标表示。现要求把这些通讯站连接成一张网络，而连线费与长度成正比，应该如何联接才能使得总费用最低？ a(0,15) b(5,20) c(16,24) d(20,20),e(33,25) f(23,11) g(35,7),h(25,0) i(10,3)

35 第6讲 图论模型 应用Kruskal算法，可以得到问题的最小生成树： 这是按照欧氏距离来算的

36 不是最优铺设方式 第6讲 图论模型 进一步从实际考虑：由于街道都呈南北和东西走向，我们考虑采用棋盘距离来求解此问题，此时
第6讲 图论模型 进一步从实际考虑：由于街道都呈南北和东西走向，我们考虑采用棋盘距离来求解此问题，此时 同样使用最小生成树算法： 不是最优铺设方式

37 第6讲 图论模型 若增加部分中间节点，可得到最优铺设方式

38 同样，我们可以建立最小生成树的线性规划模型
第6讲 图论模型 同样，我们可以建立最小生成树的线性规划模型 假设有向连通图有n个顶点，现需要求由此图生成的最小生成树.设图中(i,j)边上的权重为wij，设决策变量为xij=1说明弧(i,j)进入到最小生成树中，并且设最小生成树的根结点为v；则线性规划模型可表达为 根节点至少有一条出边 每个点有且仅有一条入边

39 第6讲 图论模型 进一步，该公司打算派人到九个通讯站进行通讯设备维护，若维护人员从a点出发，为节约开支，公司希望维护人员能够走过九个通讯站的距离最短，问如何安排维护人员维护路线？ 这个问题称为Hamilton回路问题，也是通常说的旅行商问题

40 第6讲 图论模型 定义1：包含图G中每个顶点有且仅一次的回路，称为Hamilton回路。
第6讲 图论模型 定义1：包含图G中每个顶点有且仅一次的回路，称为Hamilton回路。 对于赋权图，寻找具有最小总长度的Hamilton回路即为旅行商问题的解。 最小Hamilton回路问题是NPC问题，没有多项式解法可以解决 求解方法： （1）分枝定界：实际上是一种搜索，搜索过程中利用当前最好结果来剪枝； （2）逐次逼近：以一个初始回路为初始，通过逐步替换回路中的边同时保持回路来逐步逼近最优解； （3）进化算法（如遗传算法等）

41 同样，可以建立最小Hamilton回路的规划模型
第6讲 图论模型 同样，可以建立最小Hamilton回路的规划模型 假设图存在Hamilton回路，有n个顶点，图中(i,j)边上的权重为wij，设决策变量为xij=1说明弧(i,j)进入到Hamilton回路中，则线性规划模型可表达为 i点的出度为1 i点的入度为1 只有一个圈

42 第6讲 图论模型 优化模型求解结果:

43 6.1 用Dijkstra算法求解设备更新问题的最佳方案。 6.2 最优连线问题
第6讲 图论模型 作业： 6.1 用Dijkstra算法求解设备更新问题的最佳方案。 6.2 最优连线问题 我国西部的SV地区共有1个城市（标记为1）和9个乡镇（标记为2--10）组成，该地区不久将用上天然气，其中城市1含有井源.现要设计一供气系统，使得从城市1到每个乡镇（2--10）都有一条管道相连，并且铺设的管子的量尽可能的少.下图给出了SV地区的地理位置图，下表给出了城镇之间的距离.

44 第7讲 图论模型

45 谢 谢！