[离散数学]图论

《[离散数学]图论》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、童梦无忧网试管婴儿论坛www.tm51.com本文由rnysun贡献ppt文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。第八章图论图论(GraphTheory)图论是个应用十分广泛而又极其有趣数学分支,物理、图论是个应用十分广泛而又极其有趣数学分支物理、生物、经济、管理科学、信息论、学、生物、经济、管理科学、信息论、计算机等各个领域都可以找到图论的足迹.域都可以找到图论的足迹历史上很多数学家对图论的形成作出过贡献,历史上很多数学家对图论的形成作出过贡献特别要提与凯莱(Cayley).到的欧拉(Euler)、基尔霍夫、基尔霍夫(Kirchhoff)与凯莱与

2、凯莱欧拉在1736年发表了第一篇图论的论文解决了著名的年发表了第一篇图论的论文,欧拉在年发表了第一篇图论的论文七桥问题.拓扑学中著名的欧拉公式,也是图论中的重要七桥问题拓扑学中著名的欧拉公式也是图论中的重要公式.公式基尔霍夫对电路网络的研究(基尔霍夫定律基尔霍夫定律)以及凯莱在基尔霍夫对电路网络的研究基尔霍夫定律以及凯莱在有机化学计算中应用了树和生成树等概念.有机化学计算中应用了树和生成树等概念很多有趣的数学游戏也促进了图论的发展,如汉米尔顿很多有趣的数学游戏也促进了图论的发展如汉米尔顿周游世界游戏,四色定理等,都促进了图论的发展.周游世界游戏四色定理等都促进了图论的发展8-1.图的基

3、本概念多用户操作系统中的进程状态变换图:例1.多用户操作系统中的进程状态变换图(进程一个业务可以分成若干个阶段每个阶段看成一进程:一个业务可以分成若干个阶段进程一个业务可以分成若干个阶段,每个阶段看成一个进程.一个进程有三种状态.)个进程一个进程有三种状态进程调度re执行e就绪rI/O完成等待w请求I/OV={r,e,w}E={,,}w就绪状态:进程具备执行条件因就绪状态进程具备执行条件,因CPU少,要排队等待分配进程具备执行条件少要排队等待分配CPU.执行状态:进程已经分配到进程已经分配到CPU,它的程序正被执行它的程序正被执行.执行状态进程已经分配到它

4、的程序正被执行等待状态:进程等待某事件进程等待某事件(如完成此时就是给它CPU完成),此时就是给它等待状态进程等待某事件如I/O完成此时就是给它也不能执行..也不能执行七桥问题”哥尼斯堡城内有一条河普例2.“七桥问题”十八世纪哥尼斯堡城内有一条河普七桥问题十八世纪,哥尼斯堡城内有一条河雷格尔河,河中有两个岛屿河面架有七座桥,使得岛屿与两格尔河河中有两个岛屿,河面架有七座桥使得岛屿与两河中有两个岛屿河面架有七座桥A岸之间互相贯通.岸之间互相贯通ABCDe1ee52Be6e3e4e7CDV={A,B,C,D}E={e1,e2,e3,e4,e5e6,e7}人们茶余饭后经常到桥上散步,从而提出

5、这样问题从而提出这样问题:是否人们茶余饭后经常到桥上散步从而提出这样问题是否可以从某地出发，每座桥都走一次,再回到出发点再回到出发点.可以从某地出发，每座桥都走一次再回到出发点很多人试图找出这样的路径,都没有找到.人试图找出这样的路径都没有找到后来欧拉证明这样的路径根本不存在.的路径根本不存在此图可以抽象为上边右图.此图可以抽象为上边右图在机械加工中,经常需要在一块金属薄板上钻若干孔例3.在机械加工中经常需要在一块金属薄板上钻若干孔(或者是机械手在印刷电路板上安装电子元件如图所示或者是机械手在印刷电路板上安装电子元件)如图所示或者是机械手在印刷电路板上安装电子元件如图所示:5273问如

6、何确定钻孔的次序,使之加工的时间最短问如何确定钻孔的次序使之加工的时间最短.使之加工的时间最短这个问题可以抽象为在一个图上求从某一个结点出发,这个问题可以抽象为在一个图上求从某一个结点出发经过所有结点一次,使得此路径最短.如何找到此路径.经过所有结点一次使得此路径最短如何找到此路径类似的:旅行最优问题,工程最优问题,成本(费用最低.费用)最低类似的旅行最优问题工程最优问题成本费用最低………一.图的概念一个图G=,其中V(G):是G的结点的非空集合(V(G)≠Φ),简记成的结点的非空集合.简记成V.的结点的非空集合简记成E(G):是G的边的集合有时简记成的边的集合.

7、的边的集合有时简记成E.?结点结点(Vertices):用表示旁边标上该结点的名称表示,旁边标上该结点的名称.?边(Edges):有向边:带箭头的弧线.从u到v的边表示成有向边带箭头的弧线到的边表示成的边无向边:不带箭头的弧线和间的边不带箭头的弧线.间的边表示成无向边不带箭头的弧线u和v间的边表示成(u,v)Aree1ee52G1:Be6G2:Dwe3V(G1)={r,e,w}E(G1)={,,}Ce4e7V(G2