运筹学Ch5图与网络规划.ppt

《运筹学Ch5图与网络规划.ppt》由会员分享，可在线阅读，更多相关《运筹学Ch5图与网络规划.ppt（38页珍藏版）》请在三一办公上搜索。

1、第五章,图与网络规划,CH 5 图与网络规划,图的基本知识,最小权支撑树问题,最大流问题,最短有向路问题,学习目的,5.1 图的基本知识,一.图,Def.,一个图G是指由一集合V(G)和V(G)中某些元素的无序对的集合E(G)所构成的二元组(V(G),E(G).,V(G)称为G的顶点集,其中的元素称为G的顶点(node).,E(G)称为G的边集,其中的元素称为G的边(edge).,简计V=V(G),E=E(G).,如果V和E均为有限集合,则称G为有限图,否则称为无限图.,若边集是空集,则称该图为空图,记为;否则称其为非空图.只有一个顶点的图称为平凡图.图中顶点的个数叫做图的阶.连接同一对顶点的

2、边的条数叫做边的重数(multiplicity),若图G中存在重数大于1的边,则称G为一多重图(multigraph).,对于图G,设V=,E=.,若,则称顶点 与 是相邻的(adjacent),并称,为边e的端点,也称e与,相关联(incident).,如果,且 和 有公共的端点,则称 与 是相邻的(邻接).,若V中的某顶点和E中任何边均不关联,则称该顶点为孤立点.,两个端点重合的边称为环(loop).,没有环及没有重数大于1的边的图称为简单图(simple graph).,设有两个图,它们的顶点集间有一一对应的关系,且使得边之间有如下的关系:设,如果,则,而且 的重数与 的重数相同,这种对

3、应关系叫作同构(isomorphism).,同构关系是图之间的一个等价关系,故通常将同构的图看作是相同的.,每一对不同的顶点之间均有一条边相连的简单图称为完全图(complete graph).,Th.1:n阶完全图有 条边.,图的每条边有一个端点在 中,另一个端点在 中.,如果图的顶点能分成二个集合 与,使得同一集合中的任何两个顶点都不相邻,则称此图为二部(分)图(bipartite graph).可写成.,分划 称为图的一个二分划(bipartition).,一个完全二分图,是一个具有二分划 的简单二分图,其中 的每个顶点与 的每个顶点都相连.,设图G=(V,E),集合.令,则图 称为G的

4、补图(complement).,图H称为G的子图(subgraph),记作,若,且H中的边的重数不超过G中对应边的重数.,设,且下列三个条件中至少有一个成立:(1)(2)(3)H中至少有一个边的 重数小于G中对应边的重数,则说H是G的真子图(proper subgraph).,设图G=(V,E),一个满足,的真子图,叫做G的生成或支撑子图(spanning subgraph).,G的支撑子图,设 是图G=(V,E)的顶点集合V的一个非空子集,以 作为顶点集,以两端点均在 中的边的全体为边集的子图,称为由 导出的G的子图,记为,并称 是G的点导出子图.,若,以 中边的所有端点作为点集的子图称为由

5、 导出的子图,记为,并称 是G的边导出子图.,:以 和 的点集的交为点集,边集的交为边集.,:以 和 的点集的并为点集,边集的并为边集;,若 和 没有公共边,则称它们的边是不重的.,设 和 是G的子图,若 和 没有公共顶点,则称它们是不相交的;,两个不相交的子图,两个边不重的子图,Th.2:设G是没有孤立点的图,其边数为,若包括图G本 身和空集在内,则G的所有不同子图的个数为.,设,G中与顶点v关联的边的个数(与v关联的每个环算作两条边)称为v(在G中)的度(degree),记作,或简记为d(v).如果d(v)是奇数,则称顶点v是奇的或奇顶点(奇点);如果d(v)是偶数,则称顶点v是偶的或偶顶

6、点(偶点).,显然,若v为孤立点,则d(v)=0,且有:,Th.3:图G中所有顶点的度的和等于边数的2倍,且任意一 个图一定有偶数个奇顶点.,q 边数,图G=(V,E)中的一个顶点序列 称为是一条 途径(walk)W,若对i=1,k,有.称为W的起点,称为W的终点,称为W的内部顶点(中间点).,途径W的长度定义为它所含的边的数目,即为k.,也可以用其相应边的序列 来表示途径W,这里.,路(1 2 3 4 2 3 5 6),若在W中的顶点互不相同,则称W为一路径(初等链,初级路)(path).,由 到 的一条路,若路中的边不重复,则称为简单路.,简单图中的任一条路必为简单路,记为.,若,则称途径

7、W是闭的.,称闭途径W为一个回路或圈(cycle),如果 且 构成一路经.,简单路(1 2 5 3 4 6),初级路(1 2 3 5 6),长为偶数的圈称为偶圈,长为奇数的圈称为奇圈.,Th.4:一个图是一条路经当且仅当它中有两个顶点的度为 1,而其余顶点的度均为2.,Th.5:存在图G的顶点的一个唯一划分,使得这些 子集满足:顶点i和j位于同一子集中当且仅当G含有 一条i-j路径.,Th.6:当且仅当一个图无奇圈时,它才是二分图.,设u,v为图G中的两个顶点,若在G中存在一条u-v路径,则常称顶点u和v是连通的.如果图G中每对不同的顶点u,v间都有一条路经,则称G为连通图(connected

8、 graph),否则称为非连通图.,顶点之间的连通性是一个等价关系.,一个图G,如果能把它画在平面上,且除端点外任意两条边均不相交,则称G可嵌入平面.若图G可以嵌入平面,则称G为可平面图(planar graph).可平面图在平面上的一个嵌入称为一个平面图(plane graph).,设 为Th 5中之划分中的一个子集,则称子图 为G的一个连通分支或简称为分支(component),这里 表示两个端点均在 中的边的集合.,显然,当且仅当G只有一个分支时,G是连通图.若图G是不连通的,则其补图 连通.,二.有向图,有向图D是指由一非空有限集合V(D)和V(D)中某些元素的有序对的集合A(D)所构

9、成的二元组(V(D),A(D),V(D)称为D的顶点集,其中的元素称为D的顶点.A(D)称为D的弧(arc)集,其中的元素称为D的弧,在不至混淆时,记V=V(D),A=A(D).,起点与终点重合的弧称为环.若两条弧有相同的起点和相同的终点,则称这两条弧为重弧.既没有环也没有重弧的有向图称为简单有向图.,若u,v V,则弧a=(u,v)A是顶点u和v的有序对.常称u为弧a的起点(尾),v为a的终点(头).a称为u的出弧,也称为v的入弧.,对于有向图D的任一顶点v,以v为起点的弧的数目叫做v的出度(outdegree),记为;以v为终点的弧的数目叫做v的入度(indegree),记为.显然,.,u

10、,v,a,对一个有向图D,可以在其顶点集合上作一个图G,使得对应于D的各条弧,G有一条相同端点的边,这个无向图G称为D的基础图(underlying graph).,一般说来,对应于一个基础图可以有多个有向图.,Th.7:设D=(V,A)是一有向图，则.这里 表示集合A中的元素数目.,顶点序列 称为有向图D=(V,A)中的一条 有向途经(directed walk),若对 有.若该有向途经中的顶点互不相同,则称其为一条 有向路径;而如果,且唯一重复的顶点是,则称其为一有向回路或有向圈.,Th.8:设P是有向图D的一个子图,若 1）.2）对任意的 有.则P是一条有向i-j路径.这里V(P)表示图

11、P的顶点集.,Th.9:设C是有向图D的一个子图，若 1）对任意的,有.2）对任意的.则C是一条有向回路.,给定有向图D=(V,A),对D中的每条弧a赋予一个实数(a),称为弧a的权.是A上的一实值函数,称为D的权函数.,赋权的有向图D称为网络或赋权有向图,记为D=(V,A,).赋以权的图G称为无向网络或赋权图,记为G=(V,E,).,对于网络D=(V,A,),若 是D的一个子图,则 称为D的子网络,并定义 为子网络的权.,若对有向图D的每一对顶点,均有一条有向路径连接它们,则称D是强连通的(strongly connected).,若D是强连通的,则它亦是连通的.,割边:一条边称为G的割边,

12、如果从G中删 去它,则使图的连通分支数严格增加.,该条边不包含在G的任何简单回路中.,G=(V,E),S,T V,S T=,S,T表示一个端点在S中,而另一个端点在T中的边集合.,边割:指G的边集E的形如 的一个子集,其中S是V的非空 真子集,且若从G中删去这些边,则G的连通分 支数严格增加.,割集:G的极小边割.,每条割边均为一个割集,任何边割都是不相交割集的并,2,1,2,4,2,3割集,2,3,2,4,1,4,1,5割集,2,3,4,3,4,51,5不是割集,但为边割,2,3,2,4,1,4既非割集,亦非边割,三.图的表示,直观：,图 1,对于规模较大的图,则用一个矩阵来记录.有下列两种

13、方式:,顶点 边关联矩阵,设G=(V,E)是一个非空无环图,定义,例如,图1中所示的图G的关联矩阵为,则所得到的 阶矩阵M(G)称为图G的关联矩阵.,图的关联矩阵有下列明显的性质:,1.每一列恰好有两个非零元素1.,2.每一行的元素之和等于对应顶点的度.,3.将一个关联矩阵中的两行或两列互换,相当于在同一个图 中将两个对应的顶点或边的标号互换.,5.n阶图G是连通的当且仅当G的关联矩阵是 n-1.,4.若G有 个连通分支,则通过适当的排列 G的顶点和边所对应的行和列,G的关联矩阵可以写成块 对角形式,其中 是 的关联矩阵.,邻接矩阵,例如,图1中所示图的邻接矩阵为:,设图G=(V,E),令 等

14、于G中顶点 与 之间的边数,则 阶方阵A(G)=()称作G的邻接矩阵.,显然,1)A是一对称矩阵.,2)当图G中不存在重数大于1的边时,A的元素只取0和1 两个值.,对于有向图,亦可用类似于图的方法来表示.,例如,图2给出了一个具有五个顶点、九条弧的有向图D=(V,A).,图 2,同样,有向图也可用关联矩阵或邻接矩阵来表示.,设D=(V,A)是一非空无环有向图,定义,易知,图2中有向图的关联矩阵为,则 阶矩阵M(D)称为图D的顶点弧关联矩阵.,有向图的关联矩阵与图的关联矩阵有着类似的性质:,1.M(D)的每一列恰好有两个非零元素,一个1和一个-1.,2.M(D)的每一行中1的个数等于对应顶点的

15、入度,而-1的个数 等于对应顶点的出度.,3.将M(D)的两行或两列互换,相当于在D中将两个对应的顶 点或边的标号互换.,4.若 是D的所有连通分支,则M(D)可以写 成块对角形式,其中 为 的关联矩阵,.,5.2 树,Def.不含圈的图称为无圈图,连通的无圈图称为树.称 连通分支都是树的非连通图为森林.,如果T是G的一个支撑子图,且T是树,则称T为G的支撑树,也称为生成树.,Th.:树的性质:,1)树的顶点数比其边数多1;,2)树是无环图且树的任意两个顶点之间有唯一的一条路经;,3)在树中去掉任一条边,即变成非连通图;,4)在树中任两个不相邻顶点之间加上一条边,则构成一个恰 有一个圈的图;,

16、5)在树中至少存在两个度数为1的顶点.,Proof:,2)图G是树,任意两个顶点之间恰有一条链(路径),必要性:,G连通,任两个顶点之间至少有一条链,若某两个顶点之间有两条链,G中含有圈,与树的定义矛盾,任两个顶点之间恰有一条链,充分性:,设图G中任两个顶点之间恰有一条链,G连通,若G中含有圈,则这个圈上任两个顶点之间有两条链,与假设矛盾,G不含圈,于是G是树.,5)设图G=(V,E)是一个树,p(G)2,则G中至少有两个悬挂点.,令 是G中含边数最多的一条初等链,且G连通,P中至少有一条边,从而 与 不同,反证法.,if,则存在边,使,同理可证 也是悬挂点.,若顶点 不在P上,则 构成G中另

17、一条初等链,它含的边数比P多一条,与P是含边数最多的初等链矛盾,若点 在P上,那么 又构成G中的一个圈,这与树的定义矛盾,Th.:G有支撑树 G是连通的.,Proof:,设G有支撑树T,T连通,G具有连通的支撑子图,从而它必连通.,反之,设G连通,G的极小连通支撑子图T的每条边也都是割边,由树的性质(T为树 T 连通且每条边均是割边),T是G的一个支撑树,一个图可有多个生成树.若给图G赋以权,则称相应无向网络G中权值最小的支撑树为最小权支撑树,或简称为最小树,而称寻求该树的问题为最小树问题.,同样,把有向图D中连通、无圈的支撑子图称为D的支撑树.,如果图G中存在包含一切边的闭途径W,则称G是Euler图,W称为G的Euler闭途径.,如果有向图D中存在包含一切弧的有向闭途径W,则称D是有向Euler图,W称为D的有向Euler闭途径.,Def.,包含图G的每个顶点的路径,称为Hamilton路径,简称Hamilton路;包含G的一切顶点的圈,称为Hamilton圈(或回路).若图G包含一个Hamilton圈,则称此图为Hamilton图.,类似地,在有向图中亦可定义Hamilton圈和Hamilton路.存在Hamilton圈的有向图称为有向Hamilton图.,