西电数学建模.pptVIP

图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的某种联系，就得到了描述这个“图”的几何形象。 图论为一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。 例3 中国邮递员问题（CPP－Chinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他设计一条最短的投递路线（从邮局出发，经过投区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。 G的一条途径(walk)指一个有限非空序列它的项交替的为顶点和边，并且 的端点为 在简单图中，途径可以简单的记作 称作 的长。 赋权图 若将图G的每一条边e都对应一个实数F (e)，称F (e)为该边的权, 并称图G为赋权图(网络)，记为G = (V, E , F ). 定义 设 P ( u, v) 是赋权图G = (V, E , F ) 中从顶点u到顶点v的路, 用E ( P ) 表示路P (u, v)中全部边的集合, 记 F ( P ) = , 则称F ( P )为路P ( u, v) 的权。 定义 若 是G 中连接顶点u, v的一条路, 且对任意在G 中连接u, v的路P (u, v)都有F( ) ≤F ( P ), 则称 是G 中连接u, v的最短路。 狄克斯特拉算法 (Dijkstra algorithm, 1959) 计算两节点之间或一个节点到所有节点之间的最短路 令 表示 到 的直接距离(两点之间有边)，若两点之间没有边，令 若两点之间是有向边，则 ；令 ，s 表示始点，t 表示终点。 0、令始点 ，并用框住，所有其它节点临时标记 ； 1、从 出发，对其相邻节点 进行临时标记，有 ； 2、在所有临时标记中找出最小者，并用框住，设其为 。若此时全部节点都永久标记，算法结束；否则到下一步； 3、从新的永久标记节点 出发，对其相邻的临时标记节点进行再标记，设 为其相邻节点，则 ，返回第2步。 例 狄克斯特拉算法 3 二部图的匹配 设M是图G的的一个匹配, 其边在E\M和M中交错出现的路, 称为G的一条M–交错路. 起点和终点都未被M饱和的M –交错路, 称为M –增广路. 定理 G的一个匹配M是最大匹配的充要条件是不包含M –增广路. 二部图匹配的应用 工作安排问题 给n个工作人员 , , … , 安排n项工作 , , … , n个工作人员中每个人能胜任一项或几项工作, 但并非所有工作人员都能从事任何一项工作. 这样便提出一个问题, 对所有的工作人员能不能都分配一件他所能胜任的工作？如果不能，最多几人可以有适合的工作？ 问题转化 我们构造一个二部图G = ( X, Y), 这里 X = { , , … , },Y = { , , … , }, 并且 当且仅当工作人员 胜任工作 时, 与 才相邻. 于是, 问题转化为求二部图的一个最大匹配. 最优分派问题 在人员分派问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。 这个问题的数学模型是：在人员分派问题的模型中，图G的每条边加了权 ，表示 干工作 的效益，求加权图G上的权最大的完美匹配。 最小生成树（支撑树） 一个连通图G的生成树一般不止一棵, 图G的所有生成树中权数最小的生成树称为图G的最小生成树. Euler图和Hamilton图 定义 经过的每条边的迹叫做的Euler迹；闭的Euler迹叫做Euler回路或回路；含Euler回路的图叫做Euler图。 直观地讲，Euler图就是从一顶点出发，每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。 中国邮递员问题 一位邮递员从邮局