图论-数学建模省名师优质课获奖课件市赛课一等奖课件.ppt

1引言当然能够经过试验去尝试处理这个问题，但该城居民任何尝试均未成功。欧拉为了处理这个问题，采取了建立数学模型方法。他将每一块陆地用一个点来代替，将每一座桥用连接对应两点一条线来代替，从而得到一个有四个“点”，七条“线”“图”。问题成为从任一点出发一笔画出七条线再回到起点。欧拉考查了普通一笔画结构特点，给出了一笔画一个判定法则：这个图是连通，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”结果，不但彻底处理了这个问题，而且开创了图论研究先河。我们首先经过一些例子来了解网络优化问题。例1最短路问题（SPP－shortestpathproblem）一名货柜车司机奉命在最短时间内将一车货物从甲地运往乙地。从甲地到乙地公路网纵横交织，所以有各种行车路线，这名司机应选择哪条线路呢？假设货柜车运行速度是恒定，那么这一问题相当于需要找到一条从甲地到乙地最短路。例2公路连接问题某一地域有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都能够经高速公路直接或间接抵达另一个城市。假定已经知道了任意两个城市之间修建高速公路成本，那么应怎样决定在哪些城市间修建高速公路，使得总成本最小？例3指派问题（assignmentproblem）一家企业经理准备安排名员工去完成项任务，每人一项。因为各员工特点不一样，不一样员工去完成同一项任务时所取得回报是不一样。怎样分配工作方案能够使总回报最大？例4中国邮递员问题（CPP－chinesepostmanproblem）一名邮递员负责投递某个街区邮件。怎样为他（她）设计一条最短投递路线（从邮局出发，经过投递区内每条街道最少一次，最终返回邮局）？因为这一问题是我国管梅谷教授1960年首先提，所以国际上称之为中国邮递员问题。例5运输问题（transportationproblem）某种原材料有个产地，现在需要将原材料从产地运往个使用这些原材料工厂。假定个产地产量和家工厂需要量已知，单位产品从任一产地到任一工厂运费已知，那么怎样安排运输方案能够使总运输成本最低？上述问题有两个共同特点：一是它们目标都是从若干可能安排或方案中寻求某种意义下最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形形式直观地描述和表示，数学上把这种与图相关结构称为网络（network）。与图和网络相关最优化问题就是网络最优化或称网络优化（netwokoptimization）问题。2图与网络基本概念一个图称为有限图，假如它顶点集和边集都有限。图顶点数用符号或表示，边数用或表示。当讨论图只有一个时，总是用G来表示这个图。从而在图论符号中我们常略去字母G，比如:分别用代替。端点重合为一点边称为环(loop)。一个图称为简单图(simplegraph)，假如它既没有环也没有两条边连接同一对顶点。2.2有向图定义一个有向图（directedgraph或digraph）G是由一个非空有限集合V和V中一些元素有序对集合组成二元组，记为其中称为图顶点集或节点集.称为图弧集（arcset），A中每一个元素(即中某两个元素有序对)记为或，当弧时，称为尾（tail），为头（head）.2.3完全图、二分图每一对不一样顶点都有一条边相连简单图称为完全图(completegraph)。n个顶点完全图记为。若，，（这里表示集合X中元素个数），X中无相邻顶点对，Y中亦然，则称G为二分图(bipartitegraph)；尤其地，若，则，则称G为完全二分图，记成。2.4子图假如,,图H叫做图G子图（subgraph），记作。若H是G子图，则G称为H母图。2.5顶点度设，G中与v关联边数（每个环算作两条边）称为v度(degree)，记作。若是奇数，称v是奇顶点(oddpoint)；若是偶数，称v是偶顶点(evenpoint)。关于顶点度，我们有以下结果：(i)(ii)任意一个图奇顶点个数是偶数。2.6图与网络数据结构（i）邻接矩阵表示法例1对于所表示图，能够用邻接矩阵表示为一样，对于网络中权，也能够用类似邻接矩阵矩阵表示。只是此时一条弧所对应元素不再是1，而是对应权而已。假如网络中每条弧赋有各种权，则能够用多个矩阵表示这些权。（ii）关联矩阵表示法假如一个节点是一条弧起点，则关联矩阵中对应元素为1；假如一个节点是一条弧终点，则关联矩阵中对应元素为-1；假如一个节点与一条弧不关联，则关联矩阵中对应元素为0。例2对于例1所表示图，假如关联矩阵中每列对应弧次序为(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，则关联矩阵表示为（列单位为弧）（iii）弧表示法（iv）邻接表表示法对于有向图，普通用表示节点邻接表，即节点全部出弧组成集合或链表