您好,欢迎访问三七文档
OperationsResearch第7章图与网络优化7.1图论概述7.2图的基本概念7.3最小树问题7.4最短路问题7.5网络最大流问题7.6最小费用最大流问题7.7中国邮递员问题第1页OperationsResearch7.1图论概述图论是应用广泛的运筹学分支,在实际生活、生产和科学研究中,有很多问题可以用图论的理论和方法来解决。第2页OperationsResearch7.1图论概述欧拉七桥问题第3页欧拉回路:从图中任意一点出发,经过图中所有边一次且仅一次的回路OperationsResearch7.1图论概述环球旅行问题第4页哈密顿回路:从图中任意一点出发,经过图中所有顶点一次且仅一次的回路正十二面体正十二面体OperationsResearch7.1图论概述中国邮递员问题第5页OperationsResearch第7章图与网络优化7.1图论概述7.2图的基本概念7.3最小树问题7.4最短路问题7.5网络最大流问题7.6最小费用最大流问题7.7中国邮递员问题第6页OperationsResearch第7页北京天津郑州济南青岛徐州连云港武汉南京上海1、图及其分类7.2图的基本概念OperationsResearch7.2图的基本概念第8页1、图及其分类图论中的图是由点以及点与点之间的连线组成的示意图。用点代表所研究的对象,用连线代表两个对象之间的特定关系。BCDAABCDOperationsResearch第9页e1e2e5e3e4e6e7v2v1v3v4V={v1,v2,v3,v4}E={e1,e2,e3,e4,e5,e6,e7}e1=[v1,v2]图无向图G=(V,E)有向图D=(V,A)1、图及其分类7.2图的基本概念OperationsResearch第10页v1v3v2v5v4v6v7a1a2a3a4a5a6a7a8a9a10V={v1,v2,v3,v4,v5,v6,v7}A={a1,a2,a3,a4,a5,a6,a7,a8,a9,a10}a1=(v1,v2)1、图及其分类图无向图G=(V,E)有向图D=(V,A)7.2图的基本概念OperationsResearch第11页2、无向图的一些基本概念点数p边数qe1e2e5e3e4e6e7v2v1v3v4关联边环多重边多重图:无环,但允许有多重边的图简单图:无环,无多重边的图7.2图的基本概念OperationsResearch第12页2、无向图的一些基本概念点的次d(v):点的关联边的个数奇点注意有环时,在计算次时需要算两次。偶点悬挂点孤立点悬挂边7.2图的基本概念OperationsResearch第13页2、无向图的一些基本概念()2vVdvq[定理1]任一图中,所有点的次之和是边数的两倍。12()()()2vVvVvVdvdvdvq[定理2]任一图中,奇点的个数为偶数。关于点的次的两个定理:偶点集合奇点集合7.2图的基本概念OperationsResearch第14页2、无向图的一些基本概念链:图G=(V,E)中一个点、边交错序列中间点:除了两个端点以外的点e1e2e5e3e4e6e7v2v1v3v4v5v6v7v8v9e8e9e10(v1,e4,v4,e3,v3,e7,v6,e8,v7,e9,v5)(v1,e1,v2,e2,v3,e3,v4,e5,v5,e6,v3,e7,v6,e8,v7)圈:两个端点相同的链初等链:所有点均不相同的链简单链:所有边均不相同的链7.2图的基本概念OperationsResearch第15页2、无向图的一些基本概念连通图:任何两个点之间,至少有一条链相连的图不连通图e1e2e5e3e4e6e7v2v1v3v4v5v6v7e8e9v8v9e10连通分图:若G不是连通图,它的每一个连通的部分。7.2图的基本概念OperationsResearch第16页2、无向图的一些基本概念e1e2e5e3e4e6e7v2v1v3v4e5e3e4v2v1v3v4支撑子图:给定图G=(V,E),如果图,使及,则称G′为G的一个支撑子图。EEVVe1e2e5e3e4e7v2v3v4v1(,)GVE7.2图的基本概念OperationsResearch第17页3、有向图的一些基本概念基础图G(D):从有向图D中去掉所有弧的箭头得到的无向图。v1v3v2v5v4v6v7a1a2a3a4a5a6a7a8a9a10v1v3v2v5v4v6v7a1a2a3a4a5a6a7a8a9a107.2图的基本概念OperationsResearch第18页3、有向图的一些基本概念始点、终点弧a=(u,v)uva链、圈、初等链、初等圈、简单链、简单圈v1v3v2v5v4v6v7a1a2a3a4a5a6a7a8a9a10路:一条按照弧方向前进的链。(v1,a1,v2,a3,v3,a5,v4,a9,v6,a10,v7)回路初等路(回路)7.2图的基本概念OperationsResearch第7章图与网络优化7.1图论概述7.2图的基本概念7.3最小树问题7.4最短路问题7.5网络最大流问题7.6最小费用最大流问题7.7中国邮递员问题第19页OperationsResearch7.3最小树问题第20页例4某工厂在6个车间之间的道路网如图所示,每条道路的距离已知。问:如何沿道路架设电话线网,才能使电话线的总长最小?v1v2v3v4v5v6655124347OperationsResearch7.3最小树问题1、树的定义第21页厂长行政办公室生产办公室一车间二车间三车间四车间生产计划科技术科供销科财务科行政科设计组工艺组锻造工段锻压工段某工厂的组织机构图树:一个无圈的连通图OperationsResearch7.3最小树问题第22页2、树的6个等价性质:设图T=(V,E)是一个树,其中点数为p、边数q。(1)T为无圈的连通图;(2)T无圈,且q=p-1;(3)T连通,且q=p-1;(4)T无圈,但增加一条边,可得到一个且仅一个圈;(5)T连通,但舍弃一条边,图便不连通;(6)T中任意两个顶点之间恰有一条链。OperationsResearch7.3最小树问题图G有支撑树的充要条件是图G是连通的。第23页证明:必要性是显然的。充分性设G是连通图,若G不含圈,则G本身是一个树,从而G是它自身的一个支撑树。若G含圈,任取一个圈,从圈中去掉任意一条边,得到G的一个支撑子图G1。若G1不含圈,则G1是G的一个支撑树;否则继续上述破圈操作,直到没有圈为止,最终找到一个支撑子图,它不含圈,是G的一个支撑树。3、支撑树支撑树:若T=(V,E′)是G=(V,E)的支撑子图,且T是一个树,则T为G的一个支撑树。OperationsResearch7.3最小树问题寻找支撑树的方法:“破圈法”和“避圈法”第24页v1v3v2v5v4v6e1e2e3e4e5e6e7e8e9v1v3v2v5v4v63、支撑树OperationsResearch7.3最小树问题给图G=(V,E),对G中的每一条边[vi,vj],相应地有一个数wij,则称这样的图G为赋权图,wij称为边[vi,vj]上的权。第25页4、赋权图229312810v2v1v3v4OperationsResearch7.3最小树问题T=(V,E′)是G的一个支撑树,T中所有边的权之和为支撑树的权w(T)。如果T*的权w(T*)是G的所有支撑树的权中最小者,则称为G的最小支撑树(最小树)。第26页5、最小支撑树OperationsResearch7.3最小树问题第27页例4某工厂在6个车间之间的道路网如图所示,每条道路的距离已知。问:如何沿道路架设电话线网,才能使电话线的总长最小?v1v2v3v4v5v6655124347最小树问题就是在赋权图上求最小支撑树的问题6、最小树问题OperationsResearch7.3最小树问题第28页6、最小树问题求最小树的方法:“破圈法”和“避圈法”v1v2v3v4v5v6655124347v1v2v3v4v6v5v1v2v3v4v5v6655124347OperationsResearch第29页练习:已知世界6大城市:(Pe),(T),(Pa),(M),(N),(L)之间的交通网络的数据,确定最小树。PeTPaMNL13517768506070675957362203455城市PeTPaMNLPeT13Pa5160M777057N68673620L505925534OperationsResearch第30页G=(V,E)边e=[u,v]端点重合环多重边简单图多重图含点的次01奇数偶数孤立点悬挂点奇点偶点悬挂边点数p边数q点边关系各种链的概念链圈初等链简单链初等圈简单圈连通图连通分图支撑子图树支撑树最小树赋权图OperationsResearch第31页D=(V,A)弧a=(u,v)终点点数p弧数q点边关系各种链的概念链圈初等链简单链初等圈简单圈基础图G(D)始点路链与弧的方向一致回路初等路初等回路G=(V,E)赋权有向图OperationsResearch第7章图与网络优化7.1图论概述7.2图的基本概念7.3最小树问题7.4最短路问题7.5网络最大流问题7.6最小费用最大流问题7.7中国邮递员问题第32页OperationsResearch7.4最短路问题1、问题的提出例5如图所示的单行线交通网,通过每条单行线的费用已知。求:从v1到v8总费用最小的旅行线?第33页最短路问题是在赋权有向图中寻求最短路的问题v1v4v2v5v6v761v36101462v82243103v923OperationsResearch2、求解方法:Dijkstra算法适用范围:正费用网络(wij≥0)基本思想:第34页P标号T标号永久性标号(Permanent)临时性标号(Temporary)P(vi)最短距离T(vi)最短距离的上界7.4最短路问题OperationsResearch2、求解方法:Dijkstra算法基本步骤:第35页步骤1:如果Si=V,算法停止,则对于每个v∈Si来说,P(v)为点vs到v的最短路路长(最短路可以通过λ(v)所记录的信息反向追踪获得);否则继续步骤2。初始化。令S0={vs},P(vs)=0,λ(vs)=0;对于v≠vs,令T(v)=+∞,λ(v)=M,令k=s,即当前检查点。令Si为第i步具有P标号点的集合,P(v)表示从vs点到v点的最短距离,T(v)表示从vs点到v点的最短距离的上界,λ(v)表示从vs点到v点最短路上前一个点的标号。7.4最短路问题OperationsResearch2、求解方法:Dijkstra算法第36页步骤2:以vk为检查点,考察每个以vk为始点且属于T标号点的点vj。如果T(vj)P(vk)+wkj,则把T(vj)修改为P(vk)+wkj,且令λ(vj)=k;否则转入步骤3。步骤3:从所有T标号点中找出T(vj)最小的点,若T(vj)+∞,则把vj的T标号换成P标号P(vj)=T(vj),且令Si+1=Si+{vj},k=j,i=i+1,转入步骤1。7.4最短路问题OperationsResearch第37页v3v2例5最短路问题+∞+∞+∞0+∞+∞+∞+∞+∞1361v1v4v5v6v7v9616101462v8222343103113556610912910127.4最短路问题OperationsResearch练习:9个城市的公路网如图所示。弧上权值为两个城市之间的距离。现有一批货物从v1运到v9,问哪条路最短?第38页v8v1v2v3322.553v4v5v6v923432241v77.4最短路问题OperationsResearch6.4最短路问题第39页Dijkstra算法只适用于所有wij≥0的情形,当赋权有向图中有负权时,则算法失效。v1v2v312-37.4最短路问题OperationsResearch(,)
本文标题:图与网络优化
链接地址:https://www.777doc.com/doc-5802198 .html