资源描述：
《《运筹学图与网络》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图的基本概念与模型树图和图的最小部分树最短路问题网络的最大流第五章图与网络模型(Graphandnetworkmodeling教学目的与要求:给学生建立起用图建模的思想,学会用图分析问题.重点与难点:图的各种概念,最短路的求法,最大流的求法,其中难点是最大流的求法.教学方法:课堂讲授结合WinQSB软件的使用.思考题,讨论题,作业:本章习题.参考资料:见前言.学时分配:8学时.序言哥尼斯堡七桥问题:德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,河的两岸与岛屿之间有七座桥相互连接.当地居民热衷于一项活动,一个散步者如
2、何能走过这七座桥,且每座桥只能走一次,最终回到出发地.试验者很多,但没有人才成功.1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文,解决了著名的哥尼斯堡七桥问题.欧拉将哥尼斯堡七桥问题抽象成如下的图形:哥尼斯堡七桥问题变为,能否从图的某一点开始不重复地一笔画出这个图形.你能一笔画出吗?欧拉在论文中证明了这是不可能的.为什么?理由是:图上的每一个顶点都与奇数条边相连接,不可能一笔画出.第一节图的基本概念与基本定理一.图的基本概念日常生活中我们见过大量的图,如各种交通图,各种管网图(电网图,自来水管网,煤气管网,
3、计算机网络).都是用点表示研究对象,用线(边)表示这些对象间的关系.因此,图可以定义为点和边的集合.记作G=[V,E],其中V是点的集合,E是边的集合.在图的点和边上赋予权值(如距离,费用,容量等)则称这样的图为网络图记为N,网络图又可分有向网络图和无向网络图.名词介绍:⒈图中的点用v(vertex)表示,边用e(edge)表示,每条边用它联结的点表示,如⒉端点,关联边(incident),相邻(adjacent):若有边e可表为称为边e的端点;称边e为的关联边;若点与同一条边关联,称点相邻;若边有公共的端点,称边相邻
4、.图一⒊环(loop)多重边,简单图:如果边e的两个端点相重,称该边为环,如.如果两个端点之间多于一条边,称它具有多重边,如对于无环无多重边的图称为简单图.⒋次,奇点,偶点,孤立点,悬挂点:与某一点相关联的边的数目,称为点的次,记为如次为奇数的点称为奇点,否则称为偶点,次为1的点称为悬挂点,次为0的点称为孤立点.⒌链(chain),圈(cycle),路(route,path),回路,连通图:图中某些点和边的交替序列若其中各边互不相同,且对任意的点均相邻,称之为链.如果链中所有的顶点各不相同,这样的链称为路.判断哪一个是
5、链,哪一个是路:对起点和终点相重合的链称为圈.起点和终点重合的路称为回路.在一个图中,如果任意两点间至少存在一条链,则称该图为连通图,否则为不连通的.⒍完全图,子图,支撑子图(部分图)一个简单图中,如果任意两点之间均有边相连,称为完全图.例1有甲,乙,丙,丁,戊,己六名运动员报名参加A,B,C,D,E,F六个项目比赛.报名情况如下表,问六个项目的比赛顺序如何安排,做到每名运动员不连续参加两项比赛.ABCDEF甲***乙***丙**丁**戊***己***解:把比赛项目看作研究对象,用点表示.如果两个项目没有同一名运动员参
6、加,表明它们在比赛顺序上可排在一起,在代表这两个项目的点之间连一条线,得一图形.在该图中找一条包含全部顶点的路,就是符合要求的比赛顺序.结果:比赛顺序是A,C,B,F,E,D.练习1有甲,乙,丙,丁,戊,己六名运动员报名参加A,B,C,D,E,F六个项目比赛.报名情况如下表,问六个项目的比赛顺序如何安排,做到每名运动员不连续参加两项比赛.ABCDEF甲**乙***丙**丁**戊**己**练习2有八种化学药品A,B,C,D,P,R,S,T要放进储藏室保管,出于安全原因,下列各组药不能放在同一室内,A-R,A-C,A-T,
7、R-P,P-S,S-T,T-B,B-D,D-C,R-S,R-B,P-D,S-C,S-D,问储藏这八种药至少需几间房?具体的放置方法是什么?第二节树和图的最小部分树(最小生成树)(Treeandminimalspanningtree)树的定义:无圈的连通图称为树,记为T=(V,E).铁路的转用线,管理机构图,学科分类图,AHP决策方法等,都可用树来表示.树的特点:1.树是边数最多的无圈连通图,即在树上再任意增加一条边,必定出现圈;2.树的任意两点间,有一条且仅有一条通路.也可以说,树是最脆弱的连通图,只要在树中去掉任一条
8、边,图就不连通了.图的最小部分树(最小生成树):设是一个图,如果是的支撑子图(部分图),且是一个树,则称是的部分树.树的各条边称为树枝.在图的每条边上赋予权值的图称为赋权图.在中一般含有许多部分树,其中树枝总长为最小的部分树,称为该图的最小部分树.部分树部分树图最小部分树的求法方法一:避圈法例2如图S,A,B,C,D,E,T代表村
