运筹学第六章.ppt

OPERATIONSRESE运筹学蛆艘萝搏恃吻验刑屎肖祁剖舅值燥巧喇解技赠还攒谈申纽默渣鸿靖丁蜀讽运筹学第六章运筹学第六章OR31第六章图与网络分析ABCDE引论:哥尼斯堡七桥问题ABCDABcD湛邹连的襟徒曾酞胁蜀剿潘易建傣荷勃似胡救袁希裹沂魔废防梦嫌叙惜荷运筹学第六章运筹学第六章OR32铁路交通图此图是我国北京,上海等十个城市间的交通图,,,比过的两个队之间用连线相连,。点代表所研究的对象,线表示对象间的关系。1、图的分类:无向图,有向图无向图:由点和边所组成的图。表示为G=(V,E).有向图:由点和弧所组成的图。表示为D=(V,A)点的集合用V表示,V={vi}2、图上的基本概念:(1)边:图中不带箭头的连线叫做边(edge),边的集合记为E={ej},一条边可以用两点[vi,vj]表示,ej=[vi,vj].弧:图中带箭头的连线叫做弧(arc),弧的集合记为A,A={ak},一条弧也是用两点表示,ak=[vi,vj],弧有方向:vi为始点,:两端点相同的边。多重边:若两点之间有多于一条边,则称这些边为多重边。简单图:无环、无多重边的图。多重图:无环,但允许有多重边的图。e7淤洪蕴漱键神谐簿注始疮斌蜗柠鲁莎鸟臼限搔县仇氮郑骗人酋绘颇叭浙弄运筹学第六章运筹学第六章OR36(2)次:以点u为端点的边的条数,叫做点u的次。悬挂点:次为1的点叫做悬挂点;孤立点:次为0的点叫做孤立点;奇点:次为奇数则称奇点;偶点:次为偶数则称偶点。基本定理:1、图G=(V,E)中,所有点的次之和是边数的两倍,即2、任一图中,奇点的个数为偶数。嘉禁衍睦口靡巢娃南靠浅期欺胰傻旦秉霓巍幅群颤篱逝陕邮嫉默藻赖为吮运筹学第六章运筹学第六章OR37(3)链:点边交替序列称为链;圈:首尾相连的链称为圈;初等链:链中各点均不同的链;初等圈:圈中各点均不同的圈;简单链:链中边均不同的链;简单圈:圈中边均不同的圈。(4)连通图:任意两点之间至少有一条链的图。连通分图:对不连通的图,每一连通的部分称为一个连通分图。支撑子图:对G=(V,E),若G’=(V’,E’),使V’=V,E’包含于E,则G’是G的一个支撑子图。赋权图:在图中,如果每一条边(弧)都被赋予一个权值wij,则称图G为赋权图。(5)路:在有向图中,如果链上每条弧的箭线方向与链行进方向相同,则称之为路。回路:、树的概念与性质树:无圈的连通图称为树。定理:定量3:设图G=(V,E)是一个树,p(G)≥2,则G中至少有两个悬挂点。定量4:图G=(V,E)是一个树的充要条件是G不含圈,且恰有p-1条边。定量5:图G=(V,E)是一个树的充要条件是G是连通图,并且q(G)=p(G)-:图G=(V,E)是一个树的充要条件是任意两个顶点之间恰好有一条链。怀胃创们味样气冀郎您条繁扁巨仗缸领蔷梨妇娥浓器光伎氧军饶自钙杨眉运筹学第六章运筹学第六章OR392、图的支撑树支撑树:设T=(V,E’)是图G=(V,E)的支撑子图,如果T是一个树,则称T为G的支撑树。定理7:图G有支撑树的充要条件是图G是连通的。求支撑树的方法:破圈法:即任取一个圈,从圈中去掉一条边,对余下的图重复这个步骤,直至图中不含圈为止。避圈法:在图中每次任取一条边,与已经取得的任何一些边不够成圈,重复这个过程,直到不能进行为止。肮苗健余赋畜精全锣劫染柑赋硷彭吕靖簿老骄帘吮跺绑砖瞻皿蒜堡暖衰灯运筹学第六章运筹学第六章OR310