教案图与网络之一.ppt

1、运筹学,讲课教师：汤建影,南京航空航天大学经济与管理学院,第四章 网络分析,4.1 网络分析中的常用名词 4.2 最小生成树问题 4.3 最短路问题 4.4 最大流问题 4.5 最小费用流问题 4.6 中国邮递员问题 4.7 网络计划技术（略）,引言,哥尼斯堡七桥问题:,德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,河的两岸与岛屿之间有七座桥相互连接.当地居民热衷于一项活动,一个散步者如何能走过这七座桥,且每座桥只能走一次,最终回到出发地.试验者很多,但没有人成功.,1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文,解决了著名的哥尼斯堡七桥问题.,欧拉将哥尼斯堡七桥问题抽象成如下

2、的图形:,哥尼斯堡七桥问题变为,能否从图的某一点开始不重复地一笔画出这个图形.你能一笔画出吗?,欧拉在论文中证明了这是不可能的.为什么?,理由是:图上的每一个顶点都与奇数条边相连接,不可能一笔画出.,类似的问题,邮递员送信，要走完所负责投递的街区，完成任务后回到邮局，应当如何选择路径，使所走的路径最短 生产组织中，为完成某项生产任务，各工序之间怎样衔接，使得总工期最短 人际网络关系 铺设管道、网线、铁路，要求联接所有关键节点，而费用最省,1.1 网络分析中常用名词,图 子图和生成子图 网络图 链、路、圈和回路 连通图 简单图,1.图的基本概念,日常生活中我们见过大量的图,如各种交通图, 各种管

3、网图(电网图,自来水管网,煤气管网,计算机网络).都是用点表示研究对象,用线(边)表示这些对象间的关系.因此,图可以定义为点和边的集合.记作G=V,E,其中V是点的集合,E是边的集合.,(1)图中的点用v(vertex)表示,边用e(edge)表示,每条边用它联结的点表示,如,两点之间不带箭头(方向)的联线，称为边；带箭头(方向)的联线称为弧, 是两条不同的弧。 点与边所构成的图，称为无向图(简称图)，记为G=(V,E)；点与弧所构成的图，称为有向图，记为D=(V,A),图一,图：无向图,有向图,(2)端点,关联边(incident),相邻(adjacent): 若有边e可表为 称 为边e的端

4、点,称边e 为 的关联边; 若点 与同一条边关联,称点 相邻; 若边 有公共的端点,称边 相邻.,(3)环(loop),多重边,简单图:如果边e的两个端点相重,称该边为环,如 .如果两个端点之间多于一条边,称它具有多重边,如 ,对于无环无多重边的图称为简单图.无环但是有多重边的图称为多重图。,注意：在图论中，“环”与“圈”是两个概念。环是边的一种，圈是链的一种，是边的集合。,(4)次,奇点,偶点,孤立点,悬挂点:与某一点 相关联的边的数目,称为点 的次,记为 如 次为奇数的点称为奇点,否则称为偶点,次为1的点称为悬挂点,次为0的点称为孤立点.,定理1：图G=(V,E)中，所有点的次之和是边数的

5、两倍。 定理2：任一个图中，奇点的个数为偶数。,(5)链(chain),圈(cycle),路(route,path),回路,连通图: 图G=(V,E)中，任意一个点和边的交替序列，如,若其中各边 互不相同,且对任意的点 均相邻,称之为链.如果链中所有的顶点各不相同,这样的链称为路. 初等链：在图中，任意两点之间由顶点和边相互交替构成的一个点不重复序列。,判断 哪一个是链,哪一个是路:,对起点和终点相重合的链称为圈.起点和终点重合的路称为回路. 在一个图中,如果任意两点间至少存在一条链,则称该图为连通图,否则为不连通图.不连通图中的每一个连通部分称为该图的连通分图。,不连通图,(6)完全图,子图

6、,支撑子图(部分图),一个简单图中,如果任意两点之间均有边相连,称为完全图.,子图、生成子图、真子图,有向图D中，去除所有的弧上的箭头，即形成一个无向图G，称之为D的基础图，记为G(D) 路，回路：是相对于有向图的概念,对于无向图，路与链是一致的 路：在有向图中，方向和链的走向一致的链,针对有向图的概念,网络图,在图的各边赋予一定的物理量，例如距离，则叫做网络图。 所赋予的物理量叫做权。 权可以是：距离、时间、成本、容量等 网络图又可分有向网络图和无向网络图.,例1 有甲,乙,丙,丁,戊,己六名运动员报名参加A,B,C,D,E,F六个项目比赛.报名情况如下表,问六个项目的比赛顺序如何安排,做到

7、每名运动员不连续参加两项比赛.,解:把比赛项目看作研究对象,用点表示.如果两个项目没有同一名运动员参加,表明它们在比赛顺序上可排在一起,在代表这两个项目的点之间连一条线,得一图形.在该图中找一条包含全部顶点的路,就是符合要求的比赛顺序.,结果:比赛顺序是A,C,B,F,E,D.,练习: 有甲,乙,丙,丁,戊,己六名运动员报名参加A,B,C,D,E,F六个项目比赛.报名情况如下表,问六个项目的比赛顺序如何安排,做到每名运动员不连续参加两项比赛.,第二节 最小生成树,什么是树？ 构造生成树的方法 最小生成树问题 寻找最小生成树的方法,一、什么是树？,树：无圈的连通图，记作T=T(V,E) 树的基本

8、性质 任意两点之间有且只有一条链 若树有p个顶点，则共有q=p-1条边 若图是连通的，且q=p-1，则该图不含圈，因此是树 若图不含圈，且q=p-1，则该图联通，因此是树。 任何一个具有P个顶点，p-1条边的连通图，是树,树的应用:,管理机构图,学科分类图,AHP决策方法等,都可用树来表示.,树的特点:1.树是边数最多的无圈连通图,即在数上再任意增加一条边,必定出现圈;,2.树的任意两点间,有一条且仅有一条通路.也可以说,树是最脆弱的连通图,只要在树中去掉任一条边,图就不再连通.,树的相关定理,树中至少有两个悬挂点 图G=(V,E)是一棵树的充分必要条件是G不含圈，且恰好有p-1条边 图G=(

9、V,E)是一棵树的充分必要条件是G是连通图，且q(G)=p(G)-1 图G=(V,E)是一棵树的充分必要条件是G中任意两个顶点之间恰有一条链,二、构造生成树的方法,破圈法 避圈法,破圈法,任取一圈，从该圈中去掉任一条边 对余下的圈重复相同的步骤 直到将图中所有的圈都破掉为止,避圈法,也称为生长法 从图中某一点开始生长边 逐步扩展成长为一棵树 每步选取与已入树的边不构成圈的那些边,三、最小生成树,最小生成树的定义 最小生成树的定理,图的最小生成树(最小部分树):设 是一个图,如果 是 的支撑子图(部分图),且 是一个树,则称 是 的生成树.树的各条边称为树枝.在图的每条边上赋予权值的图称为赋权图

10、.,在 中一般含有许多生成树,其中树枝总长为最小的部分树,称为该图的最小生成树.,生成树,生成树,图,最小生成树的定义,设有一连通图G=(V,E)，对于每条边 有一个权，最小生成树问题就是求图G的一个生成树，使得是最小值,最小生成树的定理,若是图G的一棵树，当且仅当对外的每一条边， 成立，则为最小生成树。其中 是树内连接的惟一的一条链。,四、寻找最小生成树的方法,Kruskal方法(避圈法) 破圈法 矩阵计算法,Kruskal方法,例1 如图S,A,B,C,D,E,T代表村镇,村镇之间的连线上赋予了权值(可代表距离,费用,流量等)现沿图中连线架设电线,使各村镇全部通电,问如何架设使电线总长最短

11、.(该图称为赋权图或无向网络).,最小生成树总长=2+2+1+3+1+5=14,破圈法,在无向网络图N中任取一个回路,去掉这个回路中权数最大的边,得一新网络 ,在 中再任取一回路,去掉这个回路中权数最大的边,得 . 如此继续下去,直到剩下的子图中不再含回路为止,最后的这个子图为N的最小部分树.,电线总长=2+2+1+3+1+5=14,Kruskal方法(例2),矩阵计算法,首先构造一个nn阶矩阵A(n为网络顶点数)，矩阵元素 从矩阵的任一行(如第一行)开始，用适当的标号(T)标明该行对应的节点已生长入树，同时划去节点所对应的列。在以后的步骤中，被划去的元素不再作为遴选的对象以避免成圈。,矩阵计

12、算法,在有标号T的行中选取最小元素，并用方括号标明，将其所对应的边生长入树，同时在其所对应的行上标T，表明该节点已经生长入树，并划去所对应的列。 继续在有T标号的行中选取最小元素，在对应的行上标T，并划去所对应的行 重复以上步骤，直到全部节点都入树，算法停止,矩阵计算方法(求解例2),T,矩阵计算方法,T,T,矩阵计算方法,T,T,T,矩阵计算方法,T,T,T,T,矩阵计算方法,T,T,T,T,T,矩阵计算方法,T,T,T,T,T,T,矩阵计算结果,习题,P. 265，第四章习题1、2。,第三节 最短路问题,什么是最短路问题？ 求解最短路问题的基本思路 Dijstra （荷兰人）算法：标号法

13、Ford（美国人）算法：修正标号法 寻找最短路径的方法：双标号,一、什么是最短路问题？,在赋权有向图中，在给定的任意两点间寻找一条从始点到终点的路，该路的权之和最小。,最短路问题可应用于选址,管道铺设时的选线,设备更新,投资等方面.,图4-8 最短路图例,二、求解最短路问题的基本思路,使用线性规划的解法，但不能利用最短路问题的特点，使解法更有效。 利用动态规划的思路，即对于在始点到终点的总体最短路径上的任意一点，从始点到该点的最短路在总体最短路径上。 根据上述第二点，可以用标号法求解。,基本思想:最短路的子路一定还是最短路.,基本思路(例),三、Dijkstra算法,对每个节点，用两种标号：T

14、和P，表示从始点到该节点的距离，P是最短距离(权)，为永久标号，T是目前路径的距离，是临时标号。 通过不断改进T值，当其最小时，将其改为P标号。 开始时，令始点有P=0的P标号，其它节点为T=M,三、Dijkstra算法(续),标号过程分为两步： 1.修改T标号。假定是新产生的P标号点，考察以为始点的所有弧段，如果是P标号点，则对该点不再进行标号；如果 是T标号点，则进行如下修改 2.产生新的P标号点，原则：在现有的所有T标号中将值最小者改为P标号,图4-8的最短路1,图4-8的最短路2,图4-8的最短路3,图4-8的最短路4,图4-8的最短路5,图4-8的最短路6,四、Ford算法,Dijkstra算法不适用于负权网络 具有负权的网络，应当用Ford算法又叫修正标号法 修正标号法的特点是：不但最小T标号应当改为P标号，P标号也可以修改，修改后的P标号再次改为T标号。 当网络中所有顶点都是P标号时，算法才停止。,Ford算法的步骤,令网络中所有点(is)的T标号值为，即T(i)=。令始点的P标号为0,即P(s)=0 以新的P标号为始点i，检查以i为始点