运筹第5章.ppt

1、OR,图论是运筹学一个重要分支,规划论是以线性模型为研究工具，解决实际问题的优化问题。,图 论,图论是以图及其理论为研究工具，解决实际问题的优化问题。是一种全新的研究方法。,从本章开始，我们将学习图论的概念、理论、方法与应用。,图论完整 的知识体系,第五章 图的基本概念,OR,图的基本概念,连通图与子图,树,形成了,第五章 图的基本概念,OR,本章的教学目的与要求,了解图论的发展,了解图的基本概念与性质,能够运用所学知识解决一些实际问题,“学以致用” 的教学效果,达 到,第五章 图的基本概念,OR,本章教学的重点与难点,1 图的基本概念,图论的发展与拓扑学的发展密不可分,哥尼兹堡七桥问题,成为

2、了,世界 难题,“一个散步者能否走遍七座桥，且每座桥只走一次，最后回到原来出发点”。,1 图的基本概念,1736年，有人带着这个问题找到了当时的大数学家欧拉。欧拉把这个问题首先简化， 他把两座小岛和河的两岸分别看作四个点，而把七座桥看作这四个点之间的连线。,“一笔画问题”，即能不能用一笔就把这个图形画出来。,转化为,1 图的基本概念,欧拉证明了“一个图能够无重复地一笔画出”的条件： 该图必须是连通的； 与图中每一个顶点相连的边必须是偶数条。,证 明 了,结论：“不可能每座桥都走一遍，最后回到原来的位置。”,相关理论将在后续课程学习,1 图的基本概念,需要注意的是：“欧拉在解决哥尼斯堡七桥问题的

3、时候，他画的图形没有考虑它的大小、形状，仅考虑点和线的个数。这些就是拓扑学思考问题的出发点。 ”,1 图的基本概念,问题1：什么是拓扑学？ 拓扑学的英文名是Topology，直译是地志学，也就是和研究地形、地貌相类似的有关学科。 我国早期曾经翻译成“形势几何学”、“连续几何学”，但是，这几种译名都不大好理解，1956年统一的数学名词把它确定为拓扑学，这是按音译过来的。,1 图的基本概念,问题2：拓扑学与几何学有何区别？ 通常的平面几何或立体几何研究的对象是点、线、面之间的位置关系以及它们的度量性质。拓扑学对于研究对象的长短、大小、面积、体积等度量性质和数量关系都无关。 在拓扑学里没有不能弯曲的

4、元素，每一个图形的大小、形状都可以改变。这些就是拓扑学思考问题的出发点。,1 图的基本概念,四色问题,著名的“四色问题”也是与拓扑学发展有关的问题。四色问题又称四色猜想，是世界近代三大数学难题之一。 四色问题的提出来自英国。1852年，毕业于伦敦大学的弗南西斯.格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”,1 图的基本概念,网络最大流问题 1956年，Ford-Fulkerson提出了最大流的标号算法， 解决了寻求已知网络的最大流问题。,固定资产更新问题 1959年，E.D.Dijkstra提出了

5、最短路的Dijkstra算法， 解决了在有向图中任意两点之间的最短路问题。后来又把该算法用于经济管理中，解决了固定资产的的最优更新问题。,1 图的基本概念,中国邮递员问题,分子结构问题,目前，图论已经形成了一个完整的 知识体系，用于解决各个领域的优化问题。,1 图的基本概念,图的概念,概念 图是有若干“顶点”和一些顶点之间的连线(边)组成。 顶点：表示某一具体事物； 边 ：表示所连接两个事物之间的某种特殊关系。,1 图的基本概念,图的表示,几个有关概念,端点 关联边 相邻的,1 图的基本概念,图的三要素,顶点 边 边的端点,如果两个图具有相同的三要素，则称它们是“同构的”。,例题：设G=(V,

6、E)，V= v1, v2, v3, v4 E= e1， e2， e3， e4， e5， e6 e1=v1, v2 ， e2=v1, v2 ， e3=v2, v3 ， e4=v3, v4 ， e5=v1, v4 ， e6=v1, v3 试画出该图。,1 图的基本概念,“同构的”,1 图的基本概念,多重图与简单图,环,多重图,简单图,简单图,多重边,多重图,1 图的基本概念,次的概念,次，记为,悬挂点,偶点,孤立点,奇点,1 图的基本概念,定理1 图G中，所有顶点次的和等于边数的两倍。,定理2 任一图G中，奇点的个数必为偶数。,1 图的基本概念,解决实际问题的例子 有甲乙丙丁戊己6名运动员参加AB

7、CDEF6个项目的比赛，报名情况如下表所示。试安排六个项目的比赛顺序，做到每名运动员不连续参加两项比赛。,图G中，一个点和边的交替序列： ， 其中 是任意 k个自然数。,2 连通图与子图,连通图,链,如果满足： ， 则称之为从 到 的一条链。,是链吗？,2 连通图与子图,举例,右图中，点和边的交替序列：,是否为一条链？,还能找出另外一条链吗？,问题：能找到一条从v1到v7 的一条链吗？,圈的概念,2 连通图与子图,连通图概念 图G中，若任何两点之间至少存在一条链，则称该图是连通的。,2 连通图与子图,子图,子图的概念 设 ，若 ， ，称 的子图。,G1是G2的子图,2 连通图与子图,部分图 若

8、 ，则称 的一个部分图。,G1是G2的部分图,3 树,树及其性质,树 一个无圈的连通图称为树，记为 。,例 在五个城市之间架设电话线，要求任何两个城市之间都可以通话，求电话线根数最少的方案？,3 树,树的性质,任意两点之间必有且仅有一条链；,任意去掉一条边，则成为不连通的；,在不相邻的两个顶点之间添上一条边，恰好得 到一个圈；,设T为p个顶点的一棵树，则T的边数为p-1条。,3 树,图的部分树,若图 是树, 则称T为图G的一棵部分树。,图G的一棵部分树,3 树,注意： 一个图的部分树是连接这个图全部顶点的最少边数的子图。,3 树,寻求部分树的方法： 破圈法 避圈法,图G的一棵部分树,3 树,避圈法,图G的一棵部分树,3 树,例2 在下面图示的稻田中，至少挖开几条堤埂，便可浇到所有稻田？,水,1,2,3,4,5,6,7,8,9,10,11,12,解 顶点：某小块稻田 边：两块稻田间有一条堤埂,3 树,赋权图 每条边上给定一个权值 。,最小部分树 图G的最小部分树问题，就是寻求它的一棵部分树，使所有边上的权值和为最小。,寻求部分树的方法： 破圈法 避圈法,第五章 练习题,练习1 十名研究生参加六门课程的考试。由于选修内容不同，考试门数也不一样，下表为每个研究生考试课程。规定考试在三天内结束，每天上下午各安排一门。研究生提出希望每人每天最多考一门，又课程A必须安排在