资源描述：
《运筹学 Ch5 图与网络规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章图与网络规划CH5图与网络规划图的基本知识最小权支撑树问题最大流问题最短有向路问题学习目的§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的边的图称为简单图(simplegraph).设有两个图,,它们的顶点集间有一一对应的关系,且使得边之间有如下的关系:设,,,如果,则,而且的重数与的重数相同,这种对应关系叫作同构(
3、isomorphism).同构关系是图之间的一个等价关系,故通常将同构的图看作是相同的.每一对不同的顶点之间均有一条边相连的简单图称为完全图(completegraph).Th.1:n阶完全图有条边.图的每条边有一个端点在中,另一个端点在中.如果图的顶点能分成二个集合与,使得同一集合中的任何两个顶点都不相邻,则称此图为二部(分)图(bipartitegraph).可写成.分划称为图的一个二分划(bipartition).一个完全二分图,是一个具有二分划的简单二分图,其中的每个顶点与的每个顶点都相连.设图G=(V,E),集合.令,则图称为G的补图(complement).图
4、H称为G的子图(subgraph),记作,若,,且H中的边的重数不超过G中对应边的重数.设,且下列三个条件中至少有一个成立:(1)(2)(3)H中至少有一个边的重数小于G中对应边的重数,则说H是G的真子图(propersubgraph).设图G=(V,E),一个满足,的真子图,叫做G的生成或支撑子图(spanningsubgraph).4531245312G的支撑子图设是图G=(V,E)的顶点集合V的一个非空子集,以作为顶点集,以两端点均在中的边的全体为边集的子图,称为由导出的G的子图,记为,并称是G的点导出子图.若,以中边的所有端点作为点集的子图称为由导出的子图,记为,
5、并称是G的边导出子图.45312G43124312:以和的点集的交为点集,边集的交为边集.:以和的点集的并为点集,边集的并为边集;若和没有公共边,则称它们的边是不重的.设和是G的子图,若和没有公共顶点,则称它们是不相交的;3154263154264263154两个不相交的子图两个边不重的子图Th.2:设G是没有孤立点的图,其边数为,若包括图G本身和空集在内,则G的所有不同子图的个数为.设,G中与顶点v关联的边的个数(与v关联的每个环算作两条边)称为v(在G中)的度(degree),记作,或简记为d(v).如果d(v)是奇数,则称顶点v是奇的或奇顶点(奇点);如果d(v)是
6、偶数,则称顶点v是偶的或偶顶点(偶点).显然,若v为孤立点,则d(v)=0,且有:Th.3:图G中所有顶点的度的和等于边数的2倍,且任意一个图一定有偶数个奇顶点.q—边数图G=(V,E)中的一个顶点序列称为是一条途径(walk)W,若对i=1,‥‥,k,有.称为W的起点,称为W的终点,称为W的内部顶点(中间点).途径W的长度定义为它所含的边的数目,即为k.也可以用其相应边的序列来表示途径W,这里.315426315264路(12342356)若在W中的顶点互不相同,则称W为一路径(初等链,初级路)(path).315426由到的一条路,若路中的边不重复,则称为简单路.简单
7、图中的任一条路必为简单路,记为.若,则称途径W是闭的.称闭途径W为一个回路或圈(cycle),如果且构成一路经.31542631526简单路(125346)初级路(12356)长为偶数的圈称为偶圈,长为奇数的圈称为奇圈.Th.4:一个图是一条路经当且仅当它中有两个顶点的度为1,而其余顶点的度均为2.Th.5:存在图G的顶点的一个唯一划分,使得这些子集满足:顶点i和j位于同一子集中当且仅当G含有一条i-j路径.Th.6:当且仅当一个图无奇圈时,它才是二分图.设u,v为图G中的两个顶点,若在G中存在一条u-v路径,则常称顶点u和v
