当前位置：文档之家 › 基于图论的数学建模

基于图论的数学建模

  • 格式：ppt
  • 大小：397.50 KB
  • 文档页数：35

下载文档原格式

  / 35

合集下载

数学建模图论兰州交通大学

数学建模图论兰州交通大学
该问题可用专门的算法来求解。
其它相关问题
2.5 最短路问题（SPP－shortest path problem）
一名货柜车司机奉命在最短的时间内将一 车货物从甲地运往乙地。从甲地到乙地的公路 网纵横交错，因此有多种行车路线，这名司机 应选择哪条线路呢？假设货柜车的运行速度是 恒定的，那么这一问题相当于需要找到一条从 甲地到乙地的最短路。
现实生活中许多问题都可归结为由点和线组 成的图形的问题，例如，铁路交通图，公路交通 图，市区交通图，自来水管网系统，甚至电路图 在研究某些问题时也可简化为由点和线组成的图 形。
如果我们用点表示这些具体事物，用连接两 点的线段（直的或曲的）表示两个事物的特定的 联系，就得到了描述这个“图”的几何形象。 图论就是研究这些由点和线组成的图形的问题。
2.6旅行商问题（TSP－traveling salesman problem）
一名推销员准备前往若干城市推销产品。 如何为他（她）设计一条最短的旅行路线（从 驻地出发，经过每个城市恰好一次，最后返回 驻地）？这一问题的研究历史十分悠久，通常 称之为旅行商问题。
2.7 指派问题（assignment problem）
能否从某个地点出发经过每个桥一次且仅一次 然后返回出发点？
Euler的做法：
A
B
C
D
图 2.2
A
B
C
D
图 2.1
❖ 建模： 点——陆地 岛屿 边——桥
2.2 Hamilton 周游世界问题
1859年 Hamilton 提出这样一个问题：一个正 十二面体有20个顶点，它们代表世界上20个 重要城市。正十二面体的每个面均为五边形， 若两个顶点之间有边相连，则表示相应的城 市之间有航线相通。 Hamilton 提出 “能否从 某城市出发经过每个城市一次且仅一次然后 返回出发点？”

数学建模图论

数学建模图论

图论一．最短路问题问题描述：寻找最短路径就是在指定网络中两结点间找一条距离最小的路。

最短路不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。

将问题抽象为赋权有向图或无向图G ，边上的权均非负 对每个顶点定义两个标记（()l v ，()z v ），其中：()l v ：表示从顶点到v 的一条路的权 ()z v ：v 的父亲点，用以确定最短路的路线S ：具有永久标号的顶点集1.1Dijkstra 算法：即在每一步改进这两个标记，使最终()l v 为最短路的权 输入：G 的带权邻接矩阵(,)w u v 步骤：（1） 赋初值：令0()0l u =，对0v u ≠，令()l v =∞，0={u }S ，0i =。

（2） 对每个(\)i i i v S S V S ∈=（即不属于上面S 集合的点），用min{(),()()}iu S l v l u w uv ∈+代替()l v ，这里()w uv 表示顶点u 和v 之间边的权值。

计算min{()}iu S l v ∈，把达到这个最小值的一个顶点记为1i u +，令11{}i i i S S u ++=⋃。

（3） 若1i V =-，则停止；若1i V <-，则用1i +代替i ，转（2）算法结束时，从0u 到各顶点v 的距离由v 的最后一次编号()l v 给出。

在v 进入i S 之前的编号()l v 叫T 标号，v 进入i S 之后的编号()l v 叫P 标号。

算法就是不断修改各顶点的T 标号，直至获得P 标号。

若在算法运行过程中，将每一顶点获得P 标号所由来的边在图上标明，则算法结束时，0u 至各顶点的最短路也在图上标示出来了。

理解：贪心算法。

选定初始点放在一个集合里，此时权值为0初始点搜索下一个相连接点，将所有相连接的点中离初始点最近的点纳入初始点所在的集合，并更新权值。

然后以新纳入的点为起点继续搜索，直到所有的点遍历。

数学模型课件图论方法建模

数学模型课件图论方法建模

§9.2 循环比赛的排名问题问题：n 支球队参加循环比赛，两两交锋，一场决胜，不容平局，“0、1”打分。

如何排名？1．竞赛图：每对顶点之间有且只有一条有向边相连的有向图；有向边指向负方。

2．路径与完全路径：称有向图),(E V G 的一个顶点序列k i i i i v v v v 210为图),(E V G 的一条步长为k 的路径，若满足：对k j k ≤≤∀1,，均有E v v j j i i ∈-1；若还满足k i i v v =0，则称之为图),(E V G 的一条步长为k 的回（或闭）路径。

而若顶点集V 的一个全排列1210-n i i i i v v v v 构成图),(E V G 的一条路径，也称之为图),(E V G 的一条完全路径。

● 图1中：6431v v v v 、16431v v v v v 、1654321v v v v v v v 、654321v v v v v v ● 子路径、闭的完全路径3．定理：任一)2(≥∀n n 阶竞赛图),(E V G 都存在完全路径。

证明（数学归纳法）：1：2=n 时，如图3-0，命题真；2：设k n =时命题真；3：当1+=k n 时，设{}121,,,+=k k v v v v V 为顶点集，记{}k v v v V ,,21~=，~G 为图),(E V G 关于{}k v v v V ,,21~=的生成子图；由归纳假设2，在~G 中存在完全路径，不失一般性，设k k v v v v 121...-为~G 中的一条完全路径，考虑顶点1+k v 与{}k v v v V ,,21~=的邻接关系，有如下三种情形：图3-1：k k k v v v v v 1211...-+为G 中的一条完全路径；图3-2：1121...+-k k k v v v v v 为G 中的一条完全路径图3-3：k k i k i v v v v v v v 11121......-+-为G 中的一条完全路径。

数学建模-图论模型

数学建模-图论模型

思路分析
• 每学期任课老师都有一定工作量的要求往往可能要上不止一门课 程。
• 每位同学需要在学期内完成若干门课程的学习。 • 某些对上课设施有特殊要求的课程，也不可以安排在同一时间。 • 为了方便开展一些全校性的活动，有些时段不安排课程。 • 受到教室数量的限制，在同一时段无法安排太多的课程。
模型建立
• 以每个课程为顶点，任何两个顶点之间连一条边当且仅当两门课 程的任课老师为同一人，或有学生同时选了这两门课或上课教室 冲突。
• 那么一个合理的课程安排就是将图中的点进行分化，使得每一个 部分里的点为一个独立集。
• 通过极小覆盖找出图中的极 大独立集，然后删去该极大 独立集，在剩下的图中找出 极大独立集，直到剩下的图 为一个独立集。
匈牙利算法
• 饱和点：Ｍ是图Ｇ的一个匹配，若Ｇ中顶点ｖ是Ｍ中某条边的端 点，则称Ｍ饱和ｖ,否则称ｖ是Ｍ的非饱和点。
• 可扩路：一条连接两个非饱和点x和y的由Ｍ外的边和Ｍ的边交错 组成的路称为Ｍ的(x,y)可扩路。
• 算法基本步骤：
Kuhn-Munkres算法
1.2 图的独立集应用
• 问题描述：各大学学期临近结束时，需要根据老师任课 计划和学生选课情况，再结合教室资源情况安排下一学 期的课程及上课时间和地点。下表所示是某大学电信学 院的大三各专业部分课程情况。该学院每届学生按专业 分班，统一选课。另外，学院只有一间普通机房和一间 高级机房。那么应该如何合理地排这些课程呢?
则称其是双连通或强连通的。对于不是双连通的图，都可以分解成 若干个极大的双连通分支，且任意两分支之间的边是同向的。
举例：
• 右图所示竞赛图不是双连通的
•
为一条有向
的D哈密尔A顿路B。 C E

数学建模中的图论方法

数学建模中的图论方法

数学建模中的图论方法一、前言我们知道，数学建模比赛中有问题A和问题B。

一般而言，问题A是连续系统中的问题，问题B是失散系统中的问题。

因为我们在大学数学教育内容中，连续系统方面的知识的比率较大，而离散数学比率较小。

所以好多人有这样的感觉，A题下手快，而B题不好下手。

其他，在有限元素的失散系统中，相应的数学模型又可以区分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。

但是这种问题在MCM中特别少见，事实上，由于比赛是开卷的，参照有关文件，使用现成的算法解决一个P类问题，不可以显示参赛者的建模及解决实诘问题能力之大小；还有一类所谓的NP问题，这种问题每一个都还没有成立有效的算法，或许真的就不行能有有效算法来解决。

命题经常以这种NPC问题为数学背景，找一个详细的实质模型来考验参赛者。

这样增添了成立数学模型的难度。

但是这也其实不是说没法求解。

一般来说，因为问题是详细的实例，我们可以找到特其他解法，或许可以给出一个近似解。

图论作为失散数学的一个重要分支，在工程技术、自然科学和经济管理中的好多方面都能供给有力的数学模型来解决实诘问题，所以吸引了好多研究人员去研究图论中的方法和算法。

应当说，我们对图论中的经典例子或多或少仍是有一些认识的，比方，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。

图论方法已经成为数学模型中的重要方法。

好多灾题因为归纳为图论问题被奇妙地解决。

并且，从历年的数学建模比赛看，出现图论模型的频次极大，比方：AMCM90B－扫雪问题；AMCM91B－找寻最优Steiner树；AMCM92B－紧迫修复系统的研制(最小生成树)AMCM94B－计算机传输数据的最小时间(边染色问题)CMCM93B－足球队排名(特点向量法)CMCM94B－锁具装箱问题(最大独立极点集、最小覆盖等用来证明最优性)CMCM98B－灾情巡视路线(最优回路)等等。

这里面都直接或是间接用到图论方面的知识。

数学建模方法之图论模型

数学建模方法之图论模型
2) 在有向图中，从顶点v引出的边的数目称为顶点 v的出度，记为d+(v)，从顶点v引入的边的数目称为 v的入度，记为d -(v). 称d(v)= d+(v)+d -(v)为顶点v的 度或次数．
定理 d (v) 2.
vV
推论 任何图中奇点 的个数为偶数． d (v1) 4
d (u3) 1
d (u3) 2
一个顶点记为 ui1，置 Si1 Si {ui1}.
3) 若 i 1，则停Hale Waihona Puke ；若 i 1，则用 i+1 代
替i，并转2).
S0 {u0},l(u j ) , j 1,2,...,7.
u1 S0 l(u1) min{,0 1}
Dijkstra算法: 求G中从顶点u0到其余顶点的最短路.
G[{v1,v2,v3}] G[{e3,e4,e5,e6}]
3) 若 V V，且 V ，以 V 为顶点集，以两端点 均在V 中的边的全体为边集的图 G 的子图，称 为G的由V 导出的子图，记为 G[V ] .
4) 若E E，且 E ，以 E为边集，以 E 的端点 集为顶点集的图 G 的子图，称为 G 的由E 导出的
第二讲 图论模型
1. 问题引入与分析
2. 图论的基本概念
3. 最短路问题及算法
4. 最小生成树及算法
回
5. 旅行售货员问题
停
6. 模型建立与求解 下
1. 问题引入与分析
1) 98年全国大学生数学建模竞赛B题“最佳灾 情巡视路线”中的前两个问题是这样的：
今年(1998年)夏天某县遭受水灾. 为考察灾情、 组织自救，县领导决定，带领有关部门负责人到 全县各乡（镇）、村巡视. 巡视路线指从县政府 所在地出发，走遍各乡（镇）、村，又回到县政 府所在地的路线.

图论-数学建模


• 以各城镇为图G的顶点，两城镇间的直通铁路为 图G相应两顶点间的边，得图G。对G的每一边e， 赋以一个实数w(e) —直通铁路的长度，称为e的权， 得到赋权图G。G的子图的权是指子图G的各边的 权和。
• 问题就是求赋权图中指定的两个顶点u0 , v间0 的具最
小权的轨。这条轨叫做 u间0 , v的0 最短路，它的权
• 在下面数据结构的讨论中，我们首先假设 G(V,A) 是一个简单有向图 ，|V|n,|A|m，并假设V中的 顶点用自然数1,2,…n表示或编号，A中的弧用自 然数1,2,…m表示或编号。
（i）邻接矩阵表示法
• 邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图G(V,的A)邻 接矩阵是如下定义的：C是一个n*n的0-1矩阵， 即
对于有向图 G(V,A)，一般用 A(i) 表示节点 的邻接表，即节点的所有出弧构成的集合或链表 （实际上只需要列出弧的另一个端点，即弧的
头）。例如上面例子，A(1){2,3}，A(5){3,4}等。
（v）星形表示法
• 星形（star）表示法的思想与邻接表表示法的思 想有一定的相似之处。对每个节点，它也是记录 从该节点出发的所有弧，但它不是采用单向链表 而是采用一个单一的数组表示。
• 一个图称为有限图，如果它的顶点集和边集都有
限。图的顶点数用符号 | V 或| 表(G示)，边数用
| E或| 表 (示G)。
• 当讨论的图只有一个时，总是用G来表示这个图。 从而在图论符号中我们常略去字母G，例如:分别
用 V,E代,替 V(G )E ,(G )。,(G )
• 端点重合为一点的边称为环(loop)。
例2 公路连接问题
某一地区有若干个主要城市，现准备修建高速公 路把这些城市连接起来，使得从其中任何一个城 市都可以经高速公路直接或间接到达另一个城市。 假定已经知道了任意两个城市之间修建高速公路 的成本，那么应如何决定在哪些城市间修建高速 公路，使得总成本最小？

数学建模-图论

显然，V1 ∪V2= V,V1∩V2=Φ 。由握手定理
2m d(v) d(v) d(v)
vV
vV1
vV2
（*）
（*）式中2m为偶， d(v) 也为偶（因其中每个d(v)为偶）， vV2
从而推知 d(v) 也为偶，而和式中每个d(v)均为奇，故和 vV1
式中被加项的项数应为偶，这表明G 中度为奇数的点有偶数个。
则G = {V, E} 是一个图，其图形如图3.1所示。
图 3.1
例3.2 设 V = {v1, v2, v3, v4}，E = {v1v2, v1v2, v2v3}， 则G = {V, E} 是一个图，其图形如图3.2所示。
图 3.2
例 3.1 和例 3.2 都不是简单图，因为例3.1 中既 含重边（e2 与 e3）又含环（e5），而例 3.2 中含 重边（v1v2）。下图3.3给出了一个简单图。
三、图论的基本概念
3.1 图的定义 3.2 图的分类 3.3 图的同构 3.4 子图 3.5 图的运算 3.6 图的代数表示及特征
主目录
3.1 图(Graph)的定义
定义3.1 称数学结构G = {V(G), E(G), G} 为
一个图，其中V(G) = {v1, v2, …, vn} 称为图 G的顶 点集(vertex set)或节点集(node set)，V(G) 中的每 一个元素 vi（i = 1, 2, …, n）称为该图的一个顶点 (vertex)或结点(node); E(G) = {e1, e2, …, em} 称为图 G 的边集（edge set），E(G) 中的每一个元素 ek （即V(G) 中某两个元素vi, vj 的无序对）记为 ek = (vi, vj) 或 ek = vivj = vjvi（k = 1, 2, …, m），被称为 该图的一条从 vi到 vj的边(edge)；

数学建模图论案例讲解PPT学习教案

第2页/共27页
第3页/共27页
旅行商问题（TSP－traveling salesman problem）
一名推销员准备前往若干城市推销产品。如何为他（她） 设计一条最短的旅行路线（从驻地出发，经过每个城市恰好 一次，最后返回驻地）？这一问题的研究历史十分悠久，通 常称之为旅行商(推销员）问题。
每个完美匹配都是最大匹配, 反之不一定成立.
第19页/共27页
二部图的匹配、独力集 例16： 判断下图的匹配
最大匹配 非完美匹配
第20页/共27页
完美匹配
二部图的匹配、独力集
定义5 若图 G的一个顶点子集中的任意两个点都互不相 邻, 则称该顶点子集为为G的一个点独立集。图G的独立 数为G的最大点独力集所含的点数，记为 (G)
x,y E’, w(x,y)=mindG(x,y)
定理２ 加权图 G 的最佳推销员回路的权与 G’的最佳 H 圈的权相同．
第9页/共27页
推销员问题近似算法：二边逐次修正法：
（１）任取初始 H 圈: C0=v1,v2,…,vi, ,…,vj,…,vn,v1
（２）对所有的 i ,j，1<i+1<j<n,若 w(vi, vj)+w(vi+1,vj+1)<w(vi,vi+1)+w(vj,vj+1) 则在 C0 中删去边(vi,vi+1)和(vj,vj+1)而加入边(vi, vj)和(vi+1,vj+1)，形成 新的 H 圈 C，即
第15页/共27页
1994全国大学生数学建模竞赛题目
B题 锁具装箱
某厂生产一种弹子锁具, 每个锁具的钥匙有5个槽, 每个槽的高度从 {1,2,3,4,5,6}6个数(单位略)中任取一数。 由于工艺及其它原因, 制造 锁具时对5个槽的高度还有两个限制: 至少有3个不同的数; 相邻两槽 高度之差不能为5。 满足以上条件制造出来的所有互不相同的锁具称 为一批。 出来的所有互不相同的锁具称为一批。 从顾客的利益出发, 自然希望在每批锁具中"一把钥匙开一把锁"。 但是在当前工艺条件下 , 对于同一批中两个锁具是否能够互开, 有以下试验结果: 若二者相对 应的5个槽的高度中有4个相同, 另一个的高度差为1, 则可能互开; 在 其它情形下, 不可能互开。 原来, 销售部门在一批锁具中随意地取每 60个装一箱出售。 团体顾客往往购买几箱到几十箱, 他们抱怨购得的 锁具会出现互相开的情形。 现聘聘请你为顾问, 回答并解决以下问题:

数学建模-图论篇44页PPT

6、法律的基础有两个，而且只有两个……公平和实用。——伯克 7、有两种和平的暴力，那就是法律和礼节。——歌德
8、法律就是秩序，有好的法律才有好的秩序。——亚里士多德 9、上帝把法律和公平凑合在一起，可是人类却把它拆开。——查·科尔顿 10、一切法律都是无用的，因为好人用不着它们，而坏人又不会因为它们而变得规矩起来。——德谟耶克斯
数学建模-图论篇
31、只有永远躺在泥坑里的人，才不会再掉进坑里。——黑格尔 32、希望的灯一旦熄灭，生活刹那间变成了一片黑暗。——普列姆昌德 33、希望是人生的乳母。——科策布 34、形成天才的决定因素应该是勤奋。——郭沫若 35、学到很多东西的诀窍
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。