《图与网络优化》PPT课件

《《图与网络优化》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学（operationsresearch,OR）第八讲图与网络优化商学院电子商务系7/17/20211第八讲图与网络优化一.图与树二.最短路问题三.最大流问题7/17/20212一、图与树第八讲图与网络优化人们为反映一些对象之间关系时，常会用示意图。图的相关概念铁路交通图比赛情况图药品存放图7/17/20213一、图与树第八讲图与网络优化图是由一些点及一些点之间的连线(不带箭头或带箭头)组成的图形。图的相关概念两点之间不带箭头的连线称为边，带箭头的连线称为弧。如果一个图G由点及边所构成，则称之为无向图(也简称为图)，记为G=（V，E），式中V，E分别是G的点集合和边集

2、合。一条连结点Vi，Vj的边记为[Vi，Vj](或[Vj，Vi])。如果一个图D由点及弧所构成，则称为有向图，记为D=(V，A)，式中V，A分别表示D的点集合和弧集合。一条方向是从vi指向vj的弧，记为(vi,vj).7/17/20214一、图与树第八讲图与网络优化点的集合：无向图例子边的集合：7/17/20215一、图与树第八讲图与网络优化有向图例子7/17/20216一、图与树第八讲图与网络优化图的相关概念图G或D中的点数记为p(G)或p(D)，边(弧)数记为q(G)(q(D))，分别简记为p，q。若边e=［u，v］∈E，则称u，v是e的端点，也称u，v是相邻的。称e

3、是点u(及点v)的关连边。若图G中，某个边e的两个端点相同，则称e是环(如前图中的e7)。若两个点之间有多于一条的边，称这些边为多重边(如前图中的e1,e2)。7/17/20217一、图与树第八讲图与网络优化图的相关概念一个无环，无多重边的图称为简单图；一个无环，但允许有多重边的图称为多重图。以点v为端点的边的个数称为v的次，记为dG(v)或d(v)。次为奇数的点，称之为奇点；次为偶数的点，称之为偶点。称次为1的点为悬挂点，悬挂点的关连边称为悬挂边，次为零的点称为孤立点。7/17/20218一、图与树第八讲图与网络优化图的相关概念证明：显然，在计算各点的次时，每条边被它的

4、端点各用了一次。定理1图G=(V，E)中，所有点的次之和是边数的两倍，即：7/17/20219一、图与树第八讲图与网络优化图的相关概念定理2任一个图中，奇点的个数为偶数。证明:设V1和V2分别是G中奇点和偶点的集合，由定理1，有：因是偶数，也是偶数，故必定也是偶数，从而V1的点数是偶数。7/17/202110一、图与树第八讲图与网络优化图的相关概念给定一个图G=(V,E)和一个点、边交错序列,如果满足：(t=1，2，…，k-1)则称为一条联结的链，记为称点为链的中间点。7/17/202111一、图与树第八讲图与网络优化图的相关概念链中，若，则称之为一个圈，记为。若链中，点

5、都是不同的，则称之为初等链；若圈中，都是不同的，则称之为初等圈。若链(圈)中含的边均不相同，则称之为简单圈。以后说到链(圈)，除非特别交代，均指初等链(圈)。7/17/202112一、图与树第八讲图与网络优化例子是一条简单链，但不是初等链，是一条初等链。是一个初等圈，是简单圈，但不是初等圈。7/17/202113一、图与树第八讲图与网络优化连通图图G中，若任何两点之间至少有一条链，则称G是连通图，否则称为不连通图。若G是不连通图，它的每个连通的部分称为G的一个连通分图(也简称分图)。思考：右图是连通图吗？7/17/202114一、图与树第八讲图与网络优化支撑子图给了一个图

6、G=(V，E)，如果G′=(V′，E′)，使V=V′及E′∈E，则称G′是G的一个支撑子图。设v∈V(G)，用G−v表示从图G中去掉点v及v的关联边后得到的一个图。7/17/202115一、图与树第八讲图与网络优化和有向图有关的概念和术语设给定一个有向图，D=(V，A)，从D中去掉所有弧上的箭头，就得到一个无向图，称之为D的基础图，记之为G(D)。给定D中的一条弧a=(u，v)，称u为a的始点，v为a的终点，称弧a是从u指向v的。设是D中的一个点弧交错序列，如果这个序列在基础图G(D)中所对应的点边序列是一条链，则称这个点弧交错序列是D的一条链。类似定义圈和初等链(圈)。

7、如果是D中的一条链，并且对t=1，2，…，k-1，均有，称之为从的一条路。若路的第一个点和最后一点相同，则称之为回路。类似定义初等路(回路)。7/17/202116一、图与树第八讲图与网络优化例子是一个回路；是从v1到v6的路；是一条链，但不是路。注：对无向图，链与路(圈与回路)两个概念是一致的。7/17/202117一、图与树第八讲图与网络优化树树：一类极其简单然而却很有用的图。树的定义：一个无圈的连通图称为树。7/17/202118一、图与树第八讲图与网络优化树的性质定理3设图G=(V，E)是一个树，p(G)≥2，则G中至