图论教案

第六章图论1第六章图论(GraphTheory)◎知识目标：掌握图的方法与原理；图的基本概念；最小树、最短路、最大流的概念、计算与应用；了解中国邮路问题与解法。◎能力目标：通过学习，使学生掌握图的方法与原理，提高分析问题和解决问题的能力。◎本章重点：最小树、最短路、最大流的计算与应用◎本章难点：最短路的应用、最大流的计算引例：哥尼斯堡七桥问题18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里，有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发，恰好通过每座桥一次，再回到起点？欧拉于1736年研究并解决了此问题，他把问题归结为如下右图的“一笔画”问题，证明上述走法是不可能的。有关图论研究的热点问题。18世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来。当地居民热衷于一个难题：是否存在一条路线，可不重复地走遍七座桥。这就是哥尼斯堡七桥问题。L.欧拉用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画的问题。他不仅解决了此问题，且给出了连通网络可一笔画的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2。当Euler在1736年访问Konigsberg,Prussia(nowKaliningradRussia)时，他发现当地的市民正从事一项非常有趣的消遣活动。Konigsberg城中有一条名叫Pregel的河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示。后来推论出此种走法是不可能的。他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。所以每行经一点时，计算两座桥（或线），从起点离开的线与最後回到始点的线亦计算两座桥，因此每一个陆地与其他陆地连接的桥数必为偶数。七桥所成之图形中，没有一点含有偶数条数，因此上述的任务无法完成.欧拉的这个考虑非常重要，也非常巧妙，它正表明了数学家处理实际问题的独特之处——把一个实际问题抽象成合适的“数学模型”。这种研究方法就是“数学模型方法”。这并不需要运用多么深奥的理论，但想到这一点，却是解决难题的关键。接下来，欧拉运用网络中的一笔画定理为判断准则，很快地就判断出要一次不重复走遍哥尼斯堡的7座桥是不可能的。也就是说，多少年来，人们费脑费力寻找的那种不重复的路线，根本就不存在。一个曾难住了那么多人的问题，竟是这么一个出人意料的答案！第六章图论2第一节图的基本概念与模型第二节最小树问题(TheMinimumSpanningTreeProblem,MinimalSpanningTreeProblem)第三节最短路问题(TheShortest-PathProblem，Shortest-RouteProblem)第四节最大流问题(MaximumFlowProblem)第五节中国邮路问题第一节图的基本概念与模型◎知识目标：掌握图的方法与原理；图的基本概念；最小树、最短路的概念、计算与应用。◎能力目标：通过学习，使学生掌握图的方法与原理，提高分析问题和解决问题的能力。◎本节重点：图的方法与原理、最小树、最短路的计算与应用◎本节难点：最短路的应用•图论中所研究的图，是指反映或描述自然界或人类社会中，大量的事物及事物之间关系的图形。•图是由点和线组成的，或：是点和边的集合。记为G=(V,E)V——节点(node)，表示研究对象E——边(Arc)，表示研究对象之间的关系•点称为顶点或节点，它的集合用V表示，顶点通常表示有形或无形的事物。线称为边，它的集合用E表示，边通常表示事物与事物（点与点）之间的联系或特定的关系。典例:会议日程安排第六章图论3某单位要在今后的三天内召开6个会议,每天上下午各安排一个会议，参加会议的领导如下∶会议A:朱、马、牛、姬、江、姚会议B:朱、杨、张、江会议C:马、姬、侯、王、姚会议D:朱、姬、张会议E:杨、侯、王会议F:刘、杨、王、江、姚每位领导每天最多只参加一个会议。会议A要安排在第一天上午,会议F安排在第三天下午，会议B要安排在任何一天的下午。试根据上述要求排出一个会议日程表，使各位领导都能参加相应的会议。解:用节点表示会议，若两个会议能安排在一天，则用连线连接。会议日程安排如下:上午下午第一天会议AE第二天会议CB第三天会议DF例题:有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F个项目的比赛。表中打对号的是各运动员报名参加比赛的项目。问六个项目的比赛顺序应如何安排，做到每名运动员都不连续参加比赛。ABCDEF甲乙丙丁戊己√√√√√√√√√√√√√√√√BCEFDA第六章图论4解：把比赛项目作为研究对象，用点表示。如果两个项目没有同一名运动员参加，在代表这两个项目的点之间连一条线，得下图。在此图中只要找出一个点的序列，使依次排列的两个点相邻，即能做到每名运动员不连续地参加比赛。满足上述要求的点的序列可以有很多，例如A-C-B-F-E-D就是其中之一。(D-E-F-B-C-A也可)练习1十名研究生参加六门课程的考试。由于选修的课程不同，考试门数也不一样。表中给出了每个研究生应参加考试的课程（打对号的）。规定考试应在三天内结束，每天上下午各安排一门。研究生们提出希望每人每天最多考一门，又课程A必须安排在第一天上午考，课程F安排在最后一门，课程B只能安排在下午考，试列出一张满足各方面要求的考试日程表。ABCDEF12345678910√√√√√√√√√√√√√√√√√√√√√√√√√√作业有八种化学药品A、B、C、D、P、R、S、T要放进贮藏室保管。出于安全原因，下列各组药品不能贮在同一室内：A-R，A-C，A-T，R-P，P-S，S-T，T-B，T-D，B-D，D-C，R-S，R-B，P-D，S-C，S-D，问贮存这八种药品至少需要多少间贮藏室？CDEFAB第六章图论5第二节最小树问题一、基本概念1树(tree)：无圈的联通图。2支撑图（部分图）：图G1和G2的节点相同，但图G1边的集合∈G2边的集合G1G23支撑树（部分树）：若图G1是G2的支撑图，且G1是树图，则图G1是G2的支撑树。一个图的支撑树不是唯一的。4最小树（最小支撑树、最小部分树）树枝总长最短的支撑树。特点：各节点都连通且线路总长最短。二、最小树的求法1破圈法：去掉圈中的最大边，直到无圈。2避圈法：保留与节点相连的最短边，直到图中没有孤立点，成为树图。(用幻灯片演示效果更好)破圈法举例例题：用破圈法求下图的最小树。第六章图论6避圈法举例用避圈法求解图的最小树。7142567373424356241271425673734243562412第六章图论7第三节最短路问题计算方法：1Dijkstra标号法2矩阵算法（略）一、Dijkstra标号法的步骤1在始点旁边的括号内标上（0）2找出与始点相邻且最近的一点，将两点间的距离标在该点旁边的括号内。3从已标号节点出发，找出与这些节点相邻的所有未标号节点，分别将已标号节点括号内的数字与该节点到它相邻的未标号节点之间的距离相加，选取最小值，填入对应节点的括号内，并加粗相应的边，表示该节点也已标号。4重复步骤3，直到终点得到标号为止。二、Dijkstra标号法举例例题：求节点1至节点7的最短路1425673734243562412第六章图论8作业：求城市A到B的最短距离。36662425476335A2345687B1附加题(设备更新问题)某企业使用一台设备,每年年初,企业都要作出决定,如果继续使用旧的,要付维修费；若购买一台新设备,要付购买费.试制定一个5年更新计划,使总支出最少.已知设备在每年年初的购买费分别为11,11,12,12,13.使用不同时间设备所需的维修费分别为5,6,8,11,18.71425673734243562412(0)(3)(5)(4)(7)(8)(10)第六章图论9解设bi表示设备在第i年年初的购买费,ci表示设备使用i年后的维修费,V={v1,v2,…,v6},点vi表示第i年年初购进一台新设备,虚设一个点v6表示第5年年底.E={vivj|1≤i＜j≤6}.由实际问题可知,设备使用三年后应当更新,因此删除该图中v1到v5,v1到v6,v2到v6的连线；又设备使用一年后就更新则不划算,因此再删除该图中v1v2,v2v3,v3v4,v4v5,v5v6五条连线后得到从上图中容易得到v1到v6只有两条路：v1v3v6和v1v4v6.都为最短路.ijkkijicbvvF1)(第六章图论10第四节最大流问题◎知识目标：掌握最大流的概念、计算与应用，了解中国邮路问题与解法。◎能力目标：通过学习，使学生掌握最大流的计算与应用，提高分析问题和解决问题的能力。◎本节重点：最大流的计算与应用◎本节难点：最大流的计算许多系统都包含了流量问题,例如网络系统中有信息流,公路系统中有车辆流,金融系统中有资金流等.对于这样包含了流量的网络系统,探讨如何发挥网络系统的能力,使系统在一定条件限制下,通过的流量最大.一、基本概念(1)网络:已知一个赋权有向图D=(V,A)在V中指定一个发点和一个收点,其他的点为中间点.对于D中每一条弧都有一个权，称为弧的容量,D也称为容量网络,简称网络,记作D=(V,A,C).•网络上的流是指定义在弧集合上的一个函数(2)可行流若D=(V,A,C）中由到各条弧上的流量满足以下条件，则称为可行流：①容量限制条件：②平衡条件：对于发点，有对于收点，有对于中间点，有其中发点的总流出量（或收点的总流入量）称为这个可行流的流量。可行流总是存在的，例如若所有弧的流量为零，就可得到流量为零的可行流，称为零流。最大流的问题就是在给定网络Ｄ上寻找一个可行流，使其流量达到最大值。(3)增广链设为网络Ｄ中到的一条链，若上某弧方向与到链的方向相同，则称此弧为正向弧；若弧的方向与到的方向相反，则称此弧为反向弧。若Ｄ中有一个可行流通过，且满足条件：①对于，有；②对于，有。则称为由到的一条增广链。最大流定理：可行流f为最大流的充要条件是：不存在关于f的增广链。,(),(,),).ijijijijffvvfvvvvf表示弧（上的流量，简记为0ijijfCsvtv(,)(,)()sjjssjjsvvAvvAffvf(,)(,)();tjjttjjtvvAvvAffvf(,)(,)0ijjiijjivvAvvAffsvsvtvtvsvtvsvtvsvtvijijfC0ijfsvtv第六章图论11二、用标号法求解网络最大流问题标号法从一个可行流f出发（若网络中没有给定f,则可以设其为零流），反复经过标号过程与调整过程来寻找最大流。在标号法中，网络中的点可分为三类：（１）标了号且检查过的点；（２）标了号但未检查的点；（３）未标号点。前两种都称为标号点，对于标号点，它的标号包含两部分内容：第一部分指出的紧前点，第二部分表示从到的可能调整量，记为一）标号过程１．标成为标了号但未检查的点，其余点都是未标号点．２．从标了号但未检查的点出发，给它相邻的未标号点标号：若，则标这里，表示从到的可能调整量若则标这里从到的可能调整量上述标号过程结束后，便成为标了号且检查过的点，而获得标号的成为标了号但未检查的点．３．重复第２步，直至标号进行不下去，或获得标号为止．若标号进行不下去，则现在的可行流是最大流，计算停止．若获得标号，则意味着已找到一条从到的增广链，转如下调整过程．(二)调整过程首先,按的标号的第一部分,反向追踪,找出增广链,确定调整量.然后,令去掉所有标号,对新的可行流，再进行标号过程(一).jvjvsvtv().jLv(0,),ssvv这时ivjv(,),ijijijvvfC上(,()).jijvvLv()min()