第六章-运筹学图与网络优化

第六章图与网络优化第六章图与网络优化第1节图的基本概念第2节树第3节最短路问题第4节网络最大流问题第1节图的基本概念例1：我国北京、上海等十个城市间的铁路交通图如下图所示：北京徐州青岛天津济南武汉南京上海连云港郑州第1节图的基本概念例2：有甲、乙、丙、丁、戊五个球队，他们之间的比赛情况如下图所示：v甲v乙v丙v丁v戊第1节图的基本概念一、图的基本概念图：由一些点及一些点之间的连线组成。边：两点之间不带箭头的连线。弧：两点之间带箭头的连线。无向图：由点及边组成。有向图：由点及弧组成。第1节图的基本概念图例：v2v1e3e2e1v2a1a2a3v3v1第1节图的基本概念二、无向图的基本概念端点：两个点vi，vj属于V，边[vi，vj]属于E，称vi，vj是边的端点。关连边：边[vi，vj]是点vi及点vj的关连边。环：边的两个端点相同。多重边：两个点之间多于一条的边。简单图：不含环和多重边的无向图。多重图：不含环，但含有多重边的无向图。第1节图的基本概念次：以点vi为端点的边的个数。悬挂点：次为1的点。悬挂边：连结悬挂点的边。奇点：次为奇数的点。偶点：次为偶数的点。孤立点：次为零的点。第1节图的基本概念图例：v2e1v4v3v1e2v2v1e3e2e1不连通图第1节图的基本概念三、无向图的基本性质任何无向图中，顶点次数的总和等于边数的2倍。任何无向图中，次为奇数的顶点必为偶数个。第1节图的基本概念四、有向图的基本概念基础图：去掉有向图中所有弧上的箭头得到的无向图。始点、终点：弧(vi，vj)中，称vi为弧的始点，vj为弧的终点。第1节图的基本概念五、图的综合概念（一）无向图链：圈：11221111()[,](121)KKKtttkiiiiiiiiiiiiGvevevevevvtkvv无向图中一个点、边交错序列，，，，,，，，若满足，，，，称这个点边序列为连接，的链。11kkiiiiGvvvv无向图中，连结与的一条链，当与是同一个点时，称此链为圈。第1节图的基本概念初等链：链中没有重复的点。初等圈：圈中没有重复的点。简单链：链中没有重复的边。简单圈：圈中没有重复的边。第1节图的基本概念图例：问：（v1，v2，v3，v4，v5，v3，v6，v7）？（v1，v2，v3，v6，v7）？（v1，v2，v3，v4，v1）？（v4，v1，v2，v3，v5，v7，v6，v3，v4）？（v1，v2，v3，v5，v4，v3，v4，v1）？v2e1v4v3v1e2v5v6v7e3e4e5e6e7e8e9第1节图的基本概念（二）有向图链：路：11221111()121KKKtttkiiiiiiiiiiiiDvavavavavvtkvv有向图中一条链，，，，,，，，若满足=(，)(，，，)，则称这个点弧序列为从到的一条路。112211()KKKiiiiiiiDvavavavGDD有向图中一个点、弧交错序列，，，，,，，，若此序列在基础图()中所对应的点边序列是一条链，则称这个点弧序列是的链。第1节图的基本概念回路：初等路：路中没有重复的点。初等回路：回路中没有重复的点。11kkiiiiDvvvv有向图中，连结与的一条链，当与是同一个点时，称此路为回路。第1节图的基本概念图例：问：（v3，a3，v2，a5，v4，a6，v5，a8，v3）？（v1，a2，v3，a4，v4，a7，v6）？（v1，a2，v3，a8，v5，a10，v6）？（v1，a2，v3，a4，v4，a6，v5，a8，v3）？v2a1v4v3v1a2v5v6v7a6a5a4a3a10a9a8a7a11第2节树一、树的概念连通图：无向图中任意两点间至少有一条链相连。（不连通图）连通分图：不连通图中每个连通的部分。树：连通且不含圈的无向图。第2节树二、树的性质任何树中必然存在次为1的点。（1）树中次为1的点称为树叶（2）树中次大于1的点称为分枝点树的点有n个，则该树的边必有（n-1）条。任何具有n个点、（n-1）条边的连通图必是树。树中任意两点之间有且只有唯一一条链。从一个树中去掉任一条边，则余下的图必是不连通图。在树中不相邻的两个点之间添上一条边，则必得到一个圈；反之再从该圈中任意去掉一条边，则必得到一个树。第2节树图例：v2v4v1v3v5第2节树三、支撑树支撑子图：支撑树：如果图G的支撑子图是一个树T，则称树T是图G的一个支撑树。支撑树的性质：图G有支撑树的充分必要条件是图G是连通图。()()GVEGVEVVEEGG设图，，，，，称是的一个支撑子图。第2节树图例：v2v4v1v3v5v2v4v1v3v5支撑子图第2节树四、最小支撑树赋权图：最小支撑树：()ijijijijGVEGvvwGwvv图，，对中每一条边[，]，相应地有一个数，则称图为赋权图，称为边[，]上的权，表示距离、时间、费用等。[]()()()ijijvvTTGTTwTwTwTwTGTG，设是的一个支撑树，称中所有边的权之和为支撑树的权，记为，即。如果支撑树的权是所有支撑树的权中最小的，则称为的最小支撑树。第2节树最小支撑树的求解方法方法一：避圈法基本做法：首先选一条最小权的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈（每一步中，如果有两条或两条以上最小权的边，则任选一条）。第2节树例3：某工厂内联结六个车间的道路网如下图所示。已知每条道路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。v3v2v4v1v5v6615572344第2节树方法二：破圈法基本做法：任取一个圈，从圈中去掉一条权最大的边，（如果有两条或两条以上最大权的边，则任去一条），在余下图中重复这个步骤，一直到得到一个不含圈的图为止。破圈法求解例3习题6-1习题6-1：分别用避圈法和破圈法求下述图的最小支撑树。1、2、2314974363231457435741第3节最短路问题一、最短路的含义()()()()min()ijijijststijvvPDVAvvwvvDPvvwPwPPwP，赋权有向图，，图中各弧，有权，，为图中任意两点，求一条路，使它是从到的所有路中总权最小的路，即。定义：路的权是中所有弧的权之和，记为第3节最短路问题例4：某单行线交通网如下图所示，每弧旁的数字表示通过这条单行线所需要的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。v41v6v2v16v5v74106v3310124v8v9322263第3节最短路问题二、最短路问题的求解方法（一）Dijkstra方法适用条件：无负权（ωij≥0）的最短路问题基本思路：11111sntstsnsnvvvvvvvvvvv若序列，，，，是从到的最短路，则序列，，，必为从到的最短路。第3节最短路问题基本解法：标号采用两种标号：T(Temporary)标号和P(Permanent)标号，T标号为临时标号，P标号为固定标号。给vi点一个P标号时，表示从vs到vi的最短路权，vi点的标号不再改变；给vi点一个T标号时，表示从vs到vi的最短路权的上界，凡没有得到P标号的点都有T标号。方法的每一步就是把某一点的T标号改为P标号，当终点vt点得到P标号时，计算结束。第3节最短路问题具体步骤：第一，给vs标上P标号P(vs)=0，其余各点为T标号，T(vj)=+∞。第二，若vi是刚标上P标号的点，选取所有与vi有关联的弧(vi，vj)中的vj点，且vj点为T标号，去修改vj点的T标号：。第三，比较所有具有T标号的点，把最小的T标号值所对应的点改为P标号，即（如果存在两个或两个以上的最小T标号，则同时改为P标号），若所有点都获得P标号，停止计算（除去从vs到vj之间无路可走，即T(vj)=+∞=P(vj)）；否则转入第二。()min()()jjiijTvTvPv，()()min()jjjjPvTvTvvT是标号Dijkstra方法求解例4第3节最短路问题例5：用Dijkstra方法求解下图中从v1到v8的最短路。v4v6v2v1v5v7v3v84677956444155习题6-2习题6-2：用Dijkstra方法求解下列各图从v1到v7的最短路。1、v3v45v6v2v14v5v71487561246习题6-22、v3v4v6v2v1v5v759118751225612第3节最短路问题（二）赋权无向图的最短‘路’问题的求解方法赋权无向图G=(V，E)，边[vi，vj]表示既可以从vi到达vj，也可以从vj到达vi，所以边[vi，vj]可以看作是两条弧(vi，vj)和(vj，vi)，且它们具有相同的权ωij。第3节最短路问题例6：计算下图所示赋权无向图中v1到v7的最短‘路’。v3v45v6v2v14v5v71487561256第3节最短路问题小结①对于赋权无向图G=(V，E)，从始点vs到各个点的最短‘路’，即为最短链②Dijkstra方法不仅适用于赋权有向图D，也适用于赋权无向图G③Dijkstra方法直接给出某点（设为vs）到其他所有点的最短路；不能直接给出赋权图上任意两点间的最短路④Dijkstra方法只适用于全部权为非负情况，如果某权为负，则算法失效。第3节最短路问题例7：求下图中从vs到v1的最短路。vsv1v285-5权为负数习题6-3习题6-3：用Dijkstra方法求解下图从v1到v9的最短‘路’。v1v3v4v7v2v5v8v93424116562784v653第3节最短路问题三、最短路问题的应用设备更新问题第3节最短路问题例10：某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。试制定一个5年的更新计划，使总支出最少。已知设备在各年的购买费，及不同机器役龄时的维修费如下表所示：项目第1年第2年第3年第4年第5年购买费1111121213机器役龄0-11-22-33-44-5维修费5681118第3节最短路问题例10：解：转化为最短路问题点vi表示第i年年初购进一台新设备弧（vi，vj）表示第i年年初购进的设备一直使用到第j年年初权ωij表示第i年年初购进设备，一直使用到第j年年初所需支付的购买、维修的全部费用第3节最短路问题最短路问题图示：1641302218171617413022592331v1v2v3v4v5v623第4节网络最大流问题例11：已知联结某产品产地v1和销地v6的交通网，如下图所示。每一弧(vi，vj)代表从vi到vj的运输线，产品经过这条弧由vi输送到vj，弧旁的数字表示这条运输线的最大通过能力。产品经过交通网从v1输送到v6。要求制定一个运输方案，使从v1运输到v6的产品数量最多。v38v5v2v110v4v63654113517网络流量最大习题6-4第4节网络最大流问题一、基本概念和性质发点、收点、中间点、容量、网络：有向图D=(V，A)，D的每条弧(vi，vj)上有非负数cij称为弧的容量，在V中指定一点称为发点（记为vs），另一点称为收点（记为vt），其余点称为中间点，这样的D称为一个网络，记作D=(V，A，C)。流、流量：定义在网络D中的弧集合A上的一个函数f={fij}称为流，称fij为弧(vi，vj)上的流量。流的性质：①每个弧上的流量不超过该弧的容量。②中间点的净输出量为零。第4节网络最大流问题可行流：满足下述条件的流f称为可行流，记作v(f)。（1）容量限制条件：对网络D中每条弧(vi，vj)，有0≤fij≤cij（2）平衡条件：•中间点每条弧vi：流出量与流入量相等•发点vs、收点vt：从点vs流出的量等于点vt流入的量可行流的性质：可行流总是存在的。零流：网络D中所有弧的流量fij=0的可行流。第4节网络最大流问题v38v5v2v110v4v63654113517v3③