运筹学图与网络优化课件

61、辍学如磨刀之石，不见其损，日有所亏。62、奇文共欣赞，疑义相与析。63、暧暧远人村，依依墟里烟，狗吠深巷中，鸡鸣桑树颠。64、一生复能几，倏如流电惊。65、少无适俗韵，性本爱丘山。运筹学图与网络优化运筹学图与网络优化61、辍学如磨刀之石，不见其损，日有所亏。62、奇文共欣赞，疑义相与析。63、暧暧远人村，依依墟里烟，狗吠深巷中，鸡鸣桑树颠。64、一生复能几，倏如流电惊。65、少无适俗韵，性本爱丘山。运筹学图与网络优化第十章

图与网络优化图论概述图论(GraphTheory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。如，通信系统、交通运输系统、信息网络系统、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。微课在农村小学数学课堂教学中应用是一次教学改革的实践，在新技术的不断更新应用下，先进的技术在教学领域的应用也不断的深入。微课就是全新的教学模式，是对以往教学理念的冲破，在当前的农村小学数学课堂教学过程中，通过微课的应用能对小学数学课堂教学的质量提升起到促进作用。一、农村小学数学课堂教学中微课应用的优势和可行性（一）农村小学数学课堂教学中微课应用的优势。农村小学数学课堂教学过程中，对微课的应用有着诸多的优势发挥，主要是能够通过多种设备来加以支持，在教学的效率上就得到了有效提升。能够通过微课将多样化的知识得到展现，传播起来也比较方便。通过微课的应用，能对学生间的差距得到有效缩小，能对学生的认知水平得到更为详细的了解，有效帮助学生在数学知识方面得到掌握[1]。微课的利用也比较方便师生及学生间的交流，老师能够更迅速的得到信息反馈，及时的调整教学方案，在师生的交流上也能得到有效加强。（二）农村小学数学课堂教学中微课应用的可行性。将微课在农村小学数学课堂中加以应用，有着其可行性，主要是小学的数学在内容层面需要微课化。由于小学生的思维逻辑能力等各方面都没有成熟化，而数学教学中的一些内容也比较枯燥，并且有的知识也很难理解，所以通过微课的应用就能将内容进行细化，让学生能由浅及深层次化的进行学习，这样在学习的效率上就能得到有效提升。再有就是学生在当前的个性化学习的需要，也使得微课在应用上有着其可行性。在微课的教学下，就能有效满足学生的个性化需求，在学习的资源上比较广泛，让学生能够对学习的内容加以选择[2]。二、农村小学数学教学中微课制作原则及具体的应用（一）农村小学数学教学中微课制作原则分析。将微课在农村小学数学教学中加以应用，要能在设计过程中遵循相应的原则，这样才能将微课的作用得到充分的发挥。先要对学生的主体性原则充分重视，微课设计过程中，老师要能注意教学的主体是学生。所以要能将设计的主体性原则充分重视，要让设计的微课能对学生的积极性得到有效激发，让学生对课程的知识能有充分的认识和了解。再者，微课制作过程中的时间原则要能充分重视，时间原则主要是针对学生的注意力不集中考虑的。小学生处在这一阶段，注意力很难长时间保持，所以在微课的制作过程中时间不能过长，将时间控制在8-10分钟之内为宜。另外，对微课的制作还要能够将针对性的原则以及完整性原则得以遵循。对微课的制作面对的对象就是学生，所以要能结合实际，从学生实际出发进行制作，这样在针对性的制作原则下，才能将其作用得到充分的发挥[3]。还有就是要能够在有限的时间内，保持微课内容的完整性。（二）农村小学数学教学中微课具体的应用。将微课在小学数学教学过程中应用的时候，要能按照相应的步骤进行实施。微课的使用过程中都是通过视频技术加以完成的，当打开微课之后，首先呈现在学生面前的就是欢迎页面，然后再进行点击相应的页面才能够对所要学习的模块内容进行查看。教师在在课前把制作好的微视频以及测试的题目要先发给学生进行自主预习，在课堂活动方面，老师就要结合教程的内容来提出相应的问题。根据问题的难易程度来进行建立环境，学生对这一问题进行分组讨论，老师要能指导整个过程的进行流程，让学生能对老师以及学生间的交流良好的保持[4]。对微视频的应用过程中，可以通过相应的动画以及故事的形式进行引入，老师也可自己制作相应的微视频来结合教材进行情境的创设。主要是能将教学过程中的重要话题进行引出来让学生讨论，关于答案老师就要引导学生进行探索。如在小学数学教学中的几何图形的抽象问题探究中，老师就要能够通过微视频的制作进行演示，让学生能够方便的掌握。也可进行设计闯关的游戏，让学生通过游戏情节等，对其中的内容有详细的了解，从而来激发学生能够进行参与。在运用到最后的阶段，要能对相关的知识框架整理出来，让学生在复习过程中提供方便。总而言之，小学数学教学过程中，通过微课的科学制作以及应用，就能将课堂教学的氛围轻松化，让学生在愉快的学习氛围中达到高效的学习状态。这就对学生的全面能力的培养有着积极作用。此次主要从微课在农村小学数学教学中的应用优势，以及应用的可行性进行了相应分析，然后结合实际探究了微课的制作原则等，希望能在此次的努力下，为实践教学发展起到促进作用。【基金项目】本文系江苏省教育科学“十二五”规划2015年度课题“农村中学课堂教学中的公平问题及对策研究”（课题编号：B-b/2015/02/171）的阶段性成果。2015年，江苏省泰兴市第三高级中学申报的江苏省教育科学“十二五”规划课题“农村中学课堂教学中的公平问题及对策研究”正式立项以后，笔者和课题组其他成员利用《农村中学课堂教学中的公平问题问卷调查表》进行较大规模的问卷调查，并带着相关的问题深入课堂听课、调查，组织教师和学生座谈，发现农村中学的课堂教学虽然在新课改的推动下有了显著的提高和改善，但依然存在一些问题，值得我们去认真反思。一、当前农村中学课堂教学中出现的主要问题1.课堂教学的功利性太强由于高考的现实压力，家长、社会和主管部门对教育的高度关注，使“应试教育”长期影响农村中学的课堂教学模式。部分教师把《考试说明》及对应的考试的范围、内容当作课堂教学取舍的唯一标准，重教材基础知识的讲授，轻学生创新能力的培养；重学生考试分数的提高，轻孩子素质的全面发展。结果导致课堂教学“学”与“用”脱节，虽然培养了一大批所谓的“高考胜利者”，但这一模式却使学生从此失去了继续学习的兴趣和主动性，可谓舍本求末。2.课堂教学忽视学生的主体地位当前，部分教师尤其是一些所谓“有经验”的老教师，不能及时更新自身的教育理念，没有学习、使用先进的教学手段和工具，在课堂教学中仍然以完成教学计划为目的，以自己的“独角戏”为主要形式，丝毫不考虑学生对知识的接受、掌握情况，导致课堂45分钟出现教师讲得“天花乱坠”、学生却听得“昏昏欲睡”的现象。3.部分教师依赖多媒体等教学设备先进的多媒体技术运用到教学中来，引发了教学思想、教学方法的重大革新，学生学习的内容更加丰富，掌握的材料更加全面，师生的交流更加便捷，知识的检测更加及时，多媒体与网络技术受到了广大一线教师尤其是年轻教师的青睐。但也有部分年轻教师对这些先进的多媒体设备产生了依赖，一旦设备出现故障就会手足无措，这实际上是基本教学技能的严重退步，导致教育方式单一和教学质量下降。4.用形式上学生的自主学习代替教师关键知识的讲解自主学习是一种高品质的学习方式，合作学习是当下新课改重点提倡的学习途径，但这一切都离不开教师的直接引导和适时指导。在当下的农村课堂教学中，仍有部分教师片面理解这一学习模式，在课堂中出现教师“不敢讲”的现象；在一些竞赛课、观摩课中，一些专家也把“教师少讲”作为评价教学方法是否先进的标准。好像教师一旦多讲了几分钟，就会有“满堂灌”“填鸭式”教学的嫌疑。5.课堂教学中组织的活动出现“形式大于内容”的倾向新课改特别强调“学生是学习的主体”，所以教师在设计教学过程时，往往把学生能更多地参与课堂活动放在优先考虑的地位，用学生讨论、演讲、辩论等形式“充实”课堂，让课堂在一片热闹、欢快的气氛中进行。如果片面理解这一理论，那么课堂活动的设计往往是“形式大于内容”，营造的只是华而不实的表面效果。这种形式化的课堂活动，充其量仅仅起到了活跃课堂气氛的作用，失去的却是宝贵的学习时间。相比这类过分形式化的活动，有时教师精彩而富于启发性的讲解，可能学生对知识掌握的效果更好。6.课堂教学中重教学方法改革而轻学习方法的指导一些骨干教师学科素养高、教学手段先进、工作态度认真，能够积极、主动地进行课堂教学改革和尝试，但却对学生的学法指导缺乏正确的认识，也没有深入地加以研究，忽视对学生学习方法的指导。“授人以鱼，不如授人以渔。”其实，教师更应重视学生的课前预习、课堂学习、课后复习、考试方法等方面的指导和训练。二、提高农村中学课堂教学的几点反思1.构建高效的课堂教学体系要想把课堂45分钟充分、高效地利用起来，就必须要打破传统的“教师讲、学生听”的课堂教学模式，把更多的课堂时间和学习主动权交给学生，让课堂教学由原来的“套餐制”变为“点餐制”。教师讲学生迫切需要的，讲学生自主学习不能掌握的，尽量把“学生自主学习与教师讲解”相结合，把“知识的探究学习与知识的实践运用”相统一，把“教材的基础知识与课外相关知识”相融合，充分利用学生的合作、师生合作等学习形式。高效课堂的本质就是让学生愿意学，在学会学习的同时形成自主学习的能力和自我发展的潜力，从而为学生的终身学习奠定基础。2.打造开放的课堂教学模式这里的“开放”并不仅仅指教学环境、教学手段的开放，还包括课堂教学活动的开放、课堂学习资料的开放、课堂教学结果的开放。这种开放性的课堂教学，给教师的教学和管理都提出了更高的要求。课前，教师对课堂教学中可能出现的各种问题、所需的多种教学方法，都要有充分的预见性。教师要从多角度去解读和认识教材的基本内容，多方面预测学生可能出现的思维结论。在课堂教学实施过程中，教师要把课堂的全部过程真正纳入自己的掌控之中，对于出现的任何生成性问题和即时性问题都要有恰当的应对措施。3.注重心理因素对课堂教学的影响学生是否有良好的思想认识、积极的心理状态，往往也能直接影响课堂教学效果。在课堂教学中，教师需要努力激发学生的学习热情，让学生以内在驱动力保证课堂45分钟一直处于积极、高效的状态。同时，在教学评价中合理运用表扬和惩罚的方式来刺激、引导学生。表扬能给学生带来尊重、成功、自豪等心理体验，有利于学生保持更好的学习心理和状态；而批评能给学生以适时的提醒，让学生更好地调整学习状态，但课堂教学中的批评一定要注意方式、方法，千万不能损及学生的自尊、人格。4.建立民主、和谐的师生关系课堂教学本身就是教师和学生的共同体，民主平等的师生关系，也是提高课堂效率的有效方法。这就要求教师应以一种平常心来看待自己和学生，与学生建立一种相互尊重、民主平等的关系。亚里士多德曾说“吾爱吾师，但更爱真理”，所以教师要注重培养学生的批判意识，鼓励学生对权威的质疑和对教师的超越。只有教师与学生之间进行心灵的对话、人格的交流，学生才会真正体验到做人的尊严，才会享受到被尊重的生命体现，才会使课堂教学中的师生关系具有意义。5.建立科学、合理的教师评价体系社会、学校对教师的评价也是课堂教学的导向，它直接决定教师对待学生的方式。传统“应试教育”主导下的教师评价体系，大多是以学生的考试分数为衡量教师的标准，这在客观上迫使教师在课堂教学中采取一些偏激的方法和手段。因此，科学、合理地评价教师的教学工作，有利于发挥教师的创造性，提高课堂教学的公平性、民主性。教育专家叶澜说过，课堂教学蕴涵着巨大的生命活力，只有师生的生命活力在课堂教学中得到有效发挥，才能真正有助于学生的培养和教师的成长，课堂上才有真正的活力。在农村学校的课堂教学中，教师还必须关注学生的情感变化和自己的感情投入，使课堂教学不仅有“气氛”，更要有“效果”，让课堂教学真正能够成就学生、成就教师。第十章

图与网络优化图论概述图论(GraphTheory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。如，通信系统、交通运输系统、信息网络系统、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。网络规划概述网络规划(NetworkProgramming)是图论与线性规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。七桥问题七桥问题图形原理及方法

七桥问题是图论中的著名问题。1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答。原因在于该图形有顶点连接奇数条边。§10.1图的基本概念一个图(Graph)

定义为三元有序组V(G)是图的顶点集合E(G)是图的边集合记Ψ

是关联函数图的端点设G是一个图(Graph)G=(V(G),E(G))，则称e连接u和v，称u和v是e的端点。若称端点u，v与边e是关联的，称两个顶点u，v是邻接的。设G是一个图，

图10－３G的几何实现图的几何实现

一个图可用一个几何图形表示,称为图的几何实现，其中每个顶点用点表示，每条边用连接端点的线表示。图的几何实现有助与我们直观的了解图的许多性质。说明一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关系。我们常常把一个图的图形当作这个抽象图自身.并称图形的点为顶点，图形的线为边。图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。几何实现图例在一个图的几何实现中，两条边的交点可能不是图的顶点。例如下图中，它共有4个顶点，6条边；而e

3

与e

4的交点不是这个图的顶点。平面图一个图称为平面图，如它有一个平面图形，使得边与边仅在顶点相交。下图就是一个平面图。基本概念端点重合为一点的边称为环。连接同一对顶点的多条边称为多重边。在右图中，e5

是一个环，e1

与e2

是多重边，v1和e1,e2,e3是关联的，v1与v2,v3是邻接的。邻接矩阵设G是一个图，G=(V(G),E(G))，定义图G的邻接矩阵A(G)=(aij)为m×m矩阵,

aij是顶点vi与边vj相邻接的边数。其中关联矩阵设G是一个图，G=(V(G),E(G))定义图G的关联矩阵M=(mij)为m×n矩阵；其中mij是顶点vi与边ej相关联的次数，取值可能为0、1、2。注图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮与计算机中。关联矩阵和邻接矩阵统称图的矩阵表示。顶点的度设G是一个图，G=(V(G),E(G))，定义图G的顶点v的度为与顶点v相关联的边数，记作d(v)

例称度为奇数的顶点为奇点；称度为偶数的顶点为偶点。例22222224+3+3+4=14=2×7关联矩阵性质图G的关联矩阵M=(mij)为m×n矩阵；则每行元素之和等于相应顶点的度；每列元素之和等于2。因此，图G的关联矩阵M所有元素之和既等于所有顶点的度之和，又等于边数的2倍。定理设G是一个图，则推论图中奇点的数目为偶数。证明记简单图一个图称为简单图，如果它既没有环也没有多重边。下图是简单图。本书只限于讨论有限简单图，即顶点集与边集都是有限集的图。u1u2u3u4f1f2f6f3f5f4只有一个顶点的图称为平凡图；边集是空集的图称为空图。同构称G和H是同构的，记为，使得给定两个图如果存在两个一一对应同构图例图G与图H是同构的。v1v2v3v4u1u2u3u4GHe6e4e2e1e3e5f1f2f6f3f5f4完全图Kn完全图是每一对不同顶点都恰有一边的简单图；具有n个顶点的完全图记为Kn.K5二分图二分图是一个简单图，其顶点集合可分划成两个子集X与Y，使得每条边的一个端点在X，另一个端点在Y;(X,Y)也称为图的二分划。x1x2x3y1y2y3完全二分图完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连；记为Km,n，其中K3,3特殊图例K5K3,3都是极小的非平面图子图称图H是图G的子图，图G及其基本图称H是G的支撑子图，如果称H是G的真子图，若如果表示关联函数记为在H的限制。顶点导出子图设W是图G的一个非空顶点子集,以W为顶点集，以二端点均在W中的边的全体为边集的子图称为由W导出的G的子图，简称导出子图，记为G[W]。导出子图G[V-w]记为G-W，即它是从G中删除W中顶点以及与这些顶点相关联的边所得到的子图。如果W仅含一个顶点v，则把简记为。边导出子图设F是图G的非空边子集，以F为边集，以F中边的端点全体为顶点集所构成的子图称为由F导出的G的子图，简称G的边导出子图。记为G[F]。记G-F表示以E(G)\F为边集的G的支撑子图，它是从G中删除F中的边所得到的子图。如F={e}，则记。子图图例v1v2v3v4v5e1e3e2Gv1v2v3v4v5G的支撑子图G-{e1,e

2,e

3}子图图例2v2v3v4e2G-{v

1,v

5}v1v2v5G[v

1,v

2,v

5]v1v2v3v4e1e3e2G[e1,e

2,e

3]v1v2v3v4v5e1e3e2G途径顶点vk叫W的终点，顶点v0

称为W的起点，顶点vi

叫W的内部顶点，整数k称为W的长度。在简单图中，径可由顶点序列表示。图G的一个有限的点边交错序列称为从v0到vk的途径。其中vi与vi+1是边ei的顶点;路、链如果径W的边不相同，则称W为一条链，如果W顶点互不相同，则称W是一条路。链长是W中边的个数k。记路长uvwxyabdefgh路：xcwhyeuav链：wcxdyhwbvgyc圈(回路)如果途径W的起点和终点相同且有正长度，则称它是一个闭途径；如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。圈：uavbwhyeuuvwxyabdefghc定理一个图是二分图当且仅当图中不存在奇圈。Euler圈Euler圈是指过所有边一次且恰好一次的闭途径。Euler链是指过所有边一次且恰好一次的链。Euler链:ydxcwheuavfygvbwuvwxyabdefghc图例下例给出了一个图的径，链和路。径：uavfyfvgyhwbv链：wcxdyhwbvgy路：xcwhyeuav圈：uavbwhyeuEuler链:ydxcwheuavfygvbwuvwxyabdefghcEuler型定理定理2设G是连通圈，则G是Euler型的充要条件是G没有奇次数的顶点。推论1设G是一个连通图，则G有Euler链当且仅当G最多有两个奇数次数的顶点。连通性图G称为连通的，如果在G的任意两个顶点u和v中存在一条(u,v)路。不连通图至少有两个连通分支。两点顶点u和v等价当且仅当u和v中存在一条(u,v)路。ω表示G的连通分支数。§10.2树树（tree）是一个不包含圈的简单连通图。具有k个连通分支的不包含圈的图称为k--树，或森林。下图列出了具有六个顶点的不同构的树。从中可以看出，图中的每棵树都只有5条边，并且至少有2个顶点的次数是1。性质1设G是一棵树，则：

G中任意两点均有唯一的路连接。2G的边数等于顶点数减1，即3若G不是平凡图，则G至少有两个次数为1的顶点。定理1设G是一个简单图，，则下列六个命题是等价的。G是一棵树。无圈且m=n-1。 G连通且m=n-1。G连通并且每条边都是割边。G中任意两点都有唯一的路相连。G无圈，但在任意一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。支撑树图G的支撑树是G的支撑子图，并且是一棵树。每个连通图都有支撑树支撑树也称为连通图的极小连通支撑子图。很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。定理定理4设T1

和T2

是G的两个支撑树，令则T1

经过k次迭代后可得到T2。定理2设G是一个连通图，T是G的一棵支撑树，e是G的一条不属于T的边，则T+e含有G的唯一圈。定理3设T是连通图G的一棵支撑树，e是T的任意一条边，则：T（1）不包含G的割集（2）包含G的唯一的割集。最小树定理5设T是G的一个支撑树，则T是G的最小树的充分必要条件为对任意边设G是一个赋权图，T为G的一个支撑树。定义T的权为：G中权最小的支撑树称为G的最小树。定理6设T是G的支撑树，则T是G的最小树的充分必要条件为对任意边，其中为G的唯一割集。最小树算法-1-贪心算法Kruskal在1965年提出一种求最小树的所谓贪心算法。算法步骤如下Step0把边按权的大小从小到大排列得：置Step1若，则停，此时G[S]即为所求的最小树；否则，转向Step2。Step2如果G[S+{ej}]不构成回路，则令转向Step1；否则，令j=j+1转向Step2。算例图7-18展示了利用Kruskal算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图7-18v1v2v4v5v312244342v1v2v4v5v312244342图7-18-1评注Kruskal算法的总计算量为，有效性不太好。求最小树的一个好的算法是Dijkstra于1959年提出的，算法的实质是在图的个独立割集中，取每个割集的一条极小边来构成最小树。最小树算法-2-Dijkstra算法Step0置Step1取置Step2若，则停止；否则，置，返回Step1算例2图7-19展示了利用Dijkstra算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图7-19利用Dijkstra算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图7-19-1破圈法是Dijkstra算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。

Step1若G不含圈，则停止；否则在G中找一个圈C，取圈C的一条边e

，满足最小树算法-3-破圈法Step2：置G=G-e，返回Step1。

利用破圈法求图7-19的最小树的过程如图7-20所示。算例3图7-20展示了利用破圈法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图7-20v1v2v4v5v312244342v1v2v4v5v312244342图7-20-1评注上述算法都可以在图上进行。为了便于计算机计算，下面介绍Dijkstra的表上算法。给定一个赋权图G，可以相应地定义一个邻接矩阵A=(wij)，其中wij是连接顶点vi和vj的权;若vivj不是G的边，则令wij

等于无穷大。Step0：画掉第一列的所有元素（例如打上×），并在第一行的每个元素下面画一横线。Step1：在画横线的元素中找一个最小的wij

，用圆圈起来，把第j列其他元素画掉，并把第j行没有画掉的元素画上横线。Step2：如果还有没有圈起来和没有画掉的元素，则返回Step1；否则，结束。这时圈起来的元素代表最小树的边，所有圈起来的元素之和就是最小树的权。最小树算法-4-表上作业法算例用表上作业法求图7-19的最小树的过程为：最小对的权=1+2+3+2=8。v1v2v4v5v312244342最小连接问题作为最小树的应用问题之一是所谓的连接问题：欲建造一个连接若干城镇（矿区或工业区）的铁路网，给定城镇i和j之间直通线路的造价为cij，试设计一个总造价最小的铁路运输图。把每个城镇看作是具有权cij的赋权图G的一个顶点。显然连接问题可以表述成：在赋权图G中，求出具有最小权的支撑树。§10.3最短路问题Dijkstra算法求任意两点的最短路算法-Floyd算法求带负权网络图的最短路的算法用线性规划求最短路赋权图给定赋权图的一个子图H，定义H的权为H的所有边权的总和。对图G的每条边e，赋予一实数ω(e)，称为边e的权，可得一赋权图。SDBTCEA712244731555赋权图中一条路的权称为路长。在一个赋权图G上，给定两个顶点u和v，所谓u和

v最短路是指所有连接顶点u和v

的路中路长最短的路；u和v最短路的路长也称为u和v的距离。SDBTCEA712244731555如何求从u到v的最短路的长？Dijkstra算法的基本思想：(1)u0u1P设S是V的真子集，如果是从u0

到的最短路，则，并且P的段是最短的路，所以算法标号令dij表示连接顶点vi与顶点vj边上的权，即(1)公式（1）是Dijkstra算法的基础。定义结点vj

的标号为始点的标号为[0,--],表明这个点前面没有点。结点vj

的标号分为两种：临时性标号和永久性标号。如果找到一条更短的路，临时性标号即被修改，如果找不到一条更短的路，临时性标号即被改为永久性标号。Step0令始点的标号为[0,--].令i=1

Stepi

(a)对于由结点i可达的还没有永久性标号的结点j，计算其临时性标号[li+dij,i]（dij>0）.如果j

已经通过另一个结点k标号为[lj,k]且li+dij<lj,则用[li+dij,i]取代[lj,k]。(b)如果所有的结点都是永久性标号，停止。否则选择最小的临时性标号[lr,s]。令i=r

，返回Stepi.计算实例求连接S、T的最短路SDBTCEA712244731555SDBTCEA7122447315550SDBTCEA71224473155505，s4，s2，s2，sSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，sSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，CSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，BSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，ElST

=13;S-T最短路为SABEDTSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D实例评述Dijkstra算法不仅找到了所求最短路，而且找到了从S点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D注:Dijkstra算法只适用于所有wij≥0的情形，当赋权有向图中存在负权时，算法失效。如v1v2v312-3用Dijkstra算法可以得出从v1到v2的最短路的权是1，但实际上从v1到v2的最短路是（v1，v3

，v2），权是-1。下面介绍具有负权赋权有向图D的最短路的算法。不妨假设从任一点vi到任一点vj都有一条弧（如果在D中，（vi，vj

）A，则添加弧（vi，vj

）令wij=+∞）。显然，从vs到任一点vj的最短路总是从vs出发到某个点vi，再沿（vi，vj）到vj的，由前面的结论可知，从vs到vi的这条路必定是从vs到vi的最短路，所以d（vs，vj）必满足如下方程：6-1-3-283-52-111-1217-3-5例：求v1到各点的最短路。wijv1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v4023-7-7-7v5-101-3-3v610-17-1-1-1v7-1-305-5-5v8-5066

例一个连接11个城镇的交通图以及城市u与v之间的一条最短路。（粗线表示）uvuv求任意两点的最短路算法-Floyd算法这种算法用一个n阶方阵来表示一个n-结点网络.矩阵中的(i,j)-元dij

表示从i

到j边上的权,即ijkFloyd’salgorithm的基本思想：给定结点i,j

和k

，若有如下三角形，且，则从i经过k到j

比直接到j所经过路线短。此时用i→k→j

代替i→j最好.------三角形运算12453354615101234512345－310∞∞3－∞5∞10∞－615∞56－4∞∞∞4－1234512345－23451－34512－45123－51234－1234512345－310∞∞3－∞5∞10∞－615∞56－4∞∞∞4－1234512345－23451－34512－45123－51234－1234512345－310∞∞3－135∞1013－615∞56－4∞∞∞4－1234512345－23451－14511－45123－51234－1234512345－310∞∞3－135∞1013－615∞56－4∞∞∞4－1234512345－23451－14511－45123－51234－12345－3108∞3－135∞1013－615856－4∞∞∞4－1234512345－23251－14511－45223－51234－1234512345－3108∞3－135∞1013－615856－4∞∞∞4－1234512345－23251－14511－45223－51234－12345－3108253－135281013－615856－4∞∞∞4－1234512345－23231－14311－45223－51234－123451234512345－3108253－135281013－615856－4∞∞∞4－1234512345－23231－14311－45223－51234－1234512345－3108123－11591011－610856－4129104－1234512345－23241－44414－44223－54444－1234512345－3108123－11591011－610856－4129104－1234512345－23241－44414－44223－54444－1234512453354615101→2→4→5用线性规划求最短路124531001550106030求从1到2的最短路20§10.4网络最大流问题vsv1v3v4v2vt322223111网络流图设D=(V,A,W)

是一个有向网络。vs是网络的源点，vt是网络的汇点。弧上的数字是允许通过的最大流量。可行流设f是定义在弧集A上的一个函数，如果对所有弧

a

成立并且对所有中间顶点

v

成立其中，f+(v)是流出v

的流量，f

-(v)是流入v的流量。则称f

是网络D上的一个可行流。2,1vsv1v3v4v2vt3,12,12,22,13,21,01,01,1---容量限制----守恒条件流值对于源点vs和汇点vt

，流出源点vs的流量等于流入汇点vt的流量，称之为流

f

的值，记为valf

。即vsv1v3v4v2vt3,12,12,22,12,13,21,01,01,1valf=3最大流网络最大流是指给定网络上的流值最大的一个可行流。寻找给定网络的最大流及其有效算法是网络规划的一个重要问题。Ford与Fulkerson在1957年提出一个求解网络最大流问题的算法，称为Ford—Fulkerson算法。割集设S是网络的顶点子集，且割集的容量定义为最小割是指容量最小的割。定义D的一个割集，简称割为vsv1v3v4v2vt322223111定理1对于网络的任意流f和割成立证明由定义可知推论1对于网络的任意流f

和割，成立vsv1v3v4v2vt322223111注：推论2的逆命题也成立，即推论中的等式永远成立。称为最大流最小割定理，是网络理论的一个重要定理。则f

是最大流，K是最小割。如果成立推论2

设f是网络的一个可行流，

是网络的一个割，链、正向弧、反向弧设P是网络D的一条链，则P中的弧可分为两类：正向弧—弧的方向与P的走向一致；记为P+。反向弧—弧的方向与P的走向相反;记为P-。网络D的连接源点vs和汇点vt的路。vsv1v3v4v2vt322223111增广链设P是网络D的一条连接源点vs和汇点vt的链，f

是网络D上的一个可行流.如果P的每一正向弧都是不饱和弧，而P的每一反向弧的流量都为正；则称P是网络D的关于可行流f

的一条可增广链。简称增广链。可增广链上流量可以增加。vsv1v3v4v2vt3，12,12,22,22,13,21,01,11,0定理2设f

是网络D上的一个可行流，则f

是一个最大流当且仅当网络D不存在f

的增广链。证明（必要性）设f

是一个最大流，假如D中存在f

的增广链P,则可以得到一个流值更大的流f

1,使得构造过程如下：其中证明充分性设网络D不存在f

的增广链。定义S如下：从而是D的割集，进而可得

中的弧都是饱和弧，而中的弧都是0流弧，否则将产生网络D

的一条增广链。因此，f的流值等于割集

的割量，所以，

f是一个最大流。定理3在任何网络流图中，最大流的值等于最小割的容量。（最大流最小割定理）Ford—Fulkerson算法Ford—Fulkerson算法的基本思想是从任意一个可行流出发，寻找流的增广链，并在这条增广链上调整流值，进而得到一个新可行流，依次进行下去，直到一个最大流为止。定理的证明过程蕴涵着最大流算法算例求下面网络的最大流vsv1v3v4v2vt852879665图4.23初始0流先给网络赋一个初始0流f0

图4.2-1vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,∞)寻找增广链1vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,∞)(+v1,5)(+v3,2)寻找增广链2vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,∞)(+v1,5)(+v3,2)(+v2,5)寻找增广链3寻找增广链4找到流f0

的增广链P0=vsv1v2vt.vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,∞)(+v1,5)(+v3,2)(+v2,5)增量θ=5.调整流值2调整流值得流值为5的新可行流f

1

，vsv1v3v4v2vt8,55,52,08,07,0