运筹学课件ch10图与网络分析.ppt

《运筹学课件ch10图与网络分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章图与网络分析Graph&NetworkAnalysis1课件章节大纲图的基本概念树与最小支撑树的应用最短路问题网络最大流问题最小费用最大流问题21847年物理学家克希荷夫发表了关于树的第一篇论文1857年英国数学家凯莱利用树的概念研究有机化合物的分子结构1878年雪尔佛斯脱首次使用“图”这个名词1936年匈牙利数学家哥尼格发表了第一本图论专著《有限图与无限图的理论》20世纪50年代图论形成了两个本质上不同的发展方向图论系统的理论研究1736年数学家欧拉发表了关于图的第一篇论文图论的代数方向图论的最优化方向31736年瑞士数学家欧拉（E.

2、Euler)提出“七桥问题”通过每座桥刚好一次又回到原地。是否可以一笔画？41859年英国数学家哈密尔顿(Hamiltonian)用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“环球旅行”。——由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的注意和研究。——发明“环球旅行”游戏用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就被称为哈密顿问题。51850年英国人格思里提出了“四色猜想”1976年，美国数学家阿佩

3、尔与哈肯在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿个判断，终于完成了四色定理的证明。任何一个平面图，都可以用四种颜色来染色，使得任何两个相邻的区域有不同的颜色。——世界近代三大数学难题之一格思里和其弟弟格里斯德·摩尔根的好友、著名数学家哈密尔顿爵士几百年来，许多数学家致力于这项研究：格思里弟弟的老师、著名数学家德·摩尔根英国最著名数学家凯利…………1878～1880年两年间，著名的律师兼数学家肯普和泰勒两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。11年后，即1890

4、年，数学家赫伍德以自己的精确计算指出肯普的证明是错误的。不久，泰勒的证明也被人们否定了。6例2有A、B、C、D、E五个球队举行比赛，已知A队与其它各队都比赛过一次；B队和A、C队比赛过；C队和A、B、D队赛过；D队和A、C、E队比赛过；E队和A、D队比赛过。那么：这种比赛关系就可以用图来表示ABCDE点：表示球队点与点之间的连线：表示两球队间比赛过7例3五个球队之间的比赛结果是：A队胜了B、D、E队；B队胜了C队；C队胜了A、D队；D队没有胜过；E队胜了D队；——用点与点之间带箭头的线描述“胜负关系”关系A队三胜一负B队一胜一负C队两胜一负D

5、队三战三负E队一胜一负从图中可以看出各球队之间比赛情况：ABCDE那么，这种胜负关系该如何用图来描述呢？810.1图的基本概念定义一个图G是指一个二元组(V(G),E(G))，即图是由点及点之间的联线所组成。其中:1）图中的点称为图的顶点(vertex)，记为：v2）图中的连线称为图的边(edge)，记为：e＝［vi,vj]，vi、vj是边e的端点。3）图中带箭头的连线称为图的弧(arc)，记为：a＝(vi,vj)，vi、vj是弧a的端点。——要研究某些对象间的二元关系时，就可以借助于图进行研究9分类无向图：点集V和边集E构成的图称为无向图(

6、undirectedgraph)，记为：G(V，E)——若这种二元关系是对称的，则可以用无向图进行研究有向图：点集V和弧集A构成的图称为有向图(directedgraph)，记为：D(V，A)——若这种二元关系是非对称的，则可以用有向图进行研究有限图:若一个图的顶点集和边集都是有限集，则称为有限图.只有一个顶点的图称为平凡图，其他的所有图都称为非平凡图.1011121图反映对象之间关系的一种工具，与几何图形不同。2图中任何两条边只可能在顶点交叉，在别的地方是立体交叉，不是图的顶点。3图的连线不用按比例画，线段不代表真正的长度，点和线的位置有任

7、意性。4图的表示不唯一。如：以下两个图都可以描述“七桥问题”。图的特点：133奇点：次为奇数的点。4偶点：次为偶数的点。5孤立点：次为零的点。6悬挂点：次为1的点。1端点：若e=[u，v]E，则称u，v是e的端点。2点的次：以点v为端点的边的个数称为点v的次，记为：d(v)。在无向图G中，与顶点v关联的边的数目(环算两次),称为顶点v的度或次数，记为d(v)或dG(v).在有向图中，从顶点v引出的边的数目称为顶点v的出度，记为d+(v)，从顶点v引入的边的数目称为v的入度，记为d-(v).称d(v)=d+(v)+d-(v)为顶点v的度或次数

8、．点(vertex)的概念14例1G=(V,E)V＝｛v1,v2,v3,v4,v5,v6,v7｝E＝｛e1,e2,e3,e4,e5,e6,e7,e8｝奇点：v2，v