运筹学图与网络问题.pptVIP

sdadsd 第十一章 图与网络模型 一、图与网络模型介绍 二、最短路问题 三、最小生成树问题 四、最大流问题 一、图与网络模型介绍 1、引例 一群人之间存在错综的关系：赵、钱、孙、李、周。赵与钱相互认识、与孙也相互认识；钱与孙相互认识、孙与李相互认识。他们与周都不认识。 如何清晰的表示这些人之间的关系呢？ 当人数更多、人们间相互关系更复杂时，该怎样描述人们间的关系？ 一群人之间存在错综的关系：赵、钱、孙、李、周。赵与钱相互认识、与孙也相互认识；钱与孙相互认识、孙与李相互认识。他们与周都不认识。 如果我们将上面的例子中人们之间的关系由“相互认识”改变成“认识”，如赵和周之间的关系是，周认识赵而赵不认识周，这时我们如何表达人们之间的这种关系呢？ 用带箭头的线来表示人们之间的关系： 一、图与网络模型介绍 2、相关概念 （1）点、边、弧 （2）无向图、有向图 （3）链、圈、连通图 （4）路、回路 （5）权、网络 点、边、弧 点——用于表示各种事物，一般用V表示 一个图中往往有多个点，一般用v1、v2、…表示。一个图中所有的n个点构成点集V={v1、v2、…、vn} 边——用于描述事物间关系的线，一般用E表示。一个图中往往有多个边，一般用e1、e2、…表示。一个图中所有的n条边构成边集E={e1、e2、…、en} 弧——带有箭头的线，一般用A表示。一个图中的n条弧，一般用a1、a2、…表示。一个图中所有的n条边构成边集A={a1、a2、…、an} 无向图、有向图 无向图：由点和边构成的图，简称“图”，一般用G表示。G=（V，E），V是图G的点集，E是图G的边集。 有向图：由点和弧构成的图，一般用D表示。D=（V，A），V是图D的点集，A是图D的弧集。 链、圈、连通图 链：对于无向图G来说，如果存在一个点、边交错序列（v1、e1、v2、e2、…、vn）,其中边ei的起点是vi，终点是vi+1，即ei=（vi，vi+1），则称这条点、边交错序列为联结v1，vn的链。 圈：如果一条链（v1、e1、v2、e2、…、vn）中， v1=vn，则称之为圈 连通图： 对一个无向图G，若任何两个不同的点之间，至少存在一条链，则称G为连通图 路、回路 路：在有向图D中，如果存在一个点、弧交错序列： （v1、a1、v2、a2、…、vn）,其中边ai的起点是vi，终点是vi+1，即ai=（vi，vi+1），则称这条点、弧交错序列为联结v1，vn的一条路。 回路：如果路的第一个点和最后一个点相同，则称这条路为回路。 权、网络 权：当无向图G的每一条边（vi，vj） ，或有向图D的每一条弧（v’i，vj’）上都相应地有一个数来进一步说明点与点之间的关系，那么这样的数我们可以称之为权，记为wij。给无向图G或有向图D添加权的过程，通常称为赋权。 网络：我们称赋了权的有向图D为网络。 二、最短路问题 最短路问题是对一个赋权的有向图D中的指定的两个点vs到vt找到一条从vs到vt的路，使得这条路上所有弧的权数的总和最小，这条路被称为从vs到vt的最短路，这条路上所有弧的权数的总和被称之为从vs到vt的距离。 如下图，找出从v1到v4的最短路 对下图，找出从vs到vt的最短路 例1 求下图中v1到v6的最短路 有向图D=（V，A）， V={v1，v2，…，v6} A={(v1,v2) ，(v1,v4)，(v1,v3),(v2,v6), (v4,v2), (v4,v6), (v3,v5),(v3,v5), (v5,v4), (v5,v6) } cij表示vi到vj的权 例1 求下图中v1到v6的最短路 v1到vt的最短路步骤： 1、给起点v1标号（0，s） 2、确定已标号点集I，未标号点集J，找出弧集A={（vi,vj）|vi I， vj J} 3、如果弧集A=空集，那么如果vt已标号，则结束，如果vt未标号则说明不存在从v1到vt的路。否则，如果弧集A≠空集，转4 4、对A中的弧，计算sij=li+cij, 从中找出值最小的弧，给此弧标号为（sij，i） 例2 电线公司准备在甲乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短。两地交通图如下： 1、 永久标号：v1（0，s） K=1 2、I={v1}，J={v2,v3,v4,v5,v6,v7}，A={(v1, v2)，(v1, v3)} 3、A≠? 4、s12=l1+c12=0+15=15 s13=l1+c13=0+10=10 Minsij=s13,永久标号：v3=（sij,i）=（10，1） s12=l1+c12=0+15=15 K=2 2、I={v1,v3}，J={v2, v4,v5,v6,v7}，A={(v1, v2)，(v3, v2)，(v3, v5)