《图的基本概念》.ppt

该【《图的基本概念》 】是由【相惜】上传分享，文档一共【19】页，该文档可以免费在线阅读，需要了解更多关于【《图的基本概念》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。图论(GraphTheory)图论是个应用十分广泛而又极其有趣数学分支,物理、学、生物、经济、管理科学、信息论、,特别要提到的欧拉(Euler)、基尔霍夫(Kirchhoff)与凯莱(Cayley).欧拉在1736年发表了第一篇图论的论文,,(基尔霍夫定律),如汉米尔顿周游世界游戏,四色定理等,:(进程:一个业务可以分成假设干个阶段,.)就绪状态:进程具备执行条件,因CPU少,??w?eV={r,e,w}E={<r,e>,<e,w>,<w,r>}执行状态:进程已经分配到CPU,:进程等待某事件(如I/O完成),此时就是给它CPU也不能执行..精选课件例2.“七桥问题〞十八世纪,哥尼斯堡城内有一条河----普雷格尔河,河中有两个岛屿,河面架有七座桥,={A,B,C,D}E={e1,e2,e3,e4,e5e6,e7}人们茶余饭后经常到桥上散步,从而提出这样问题:是否可以从某地出发,每座桥都走一次,,?B?C??,经常需要在一块金属薄板上钻假设干孔(或者是机械手在印刷电路板上安装电子元件)如下图:问如何确定钻孔的次序,,经过所有结点一次,:旅行最优问题,工程最优问题,本钱(费用)最低.…...??????????????=<V(G),E(G)>,其中V(G):是G的结点的非空集合.(V(G)≠Φ),(G):(Vertices):用?表示,(Edges):有向边:<u,v>无向边:(u,v)r??w?eV(G1)={r,e,w}E(G1)={<r,e>,<e,w>,<w,r>}A?B?C??De1e5e7e6e3e4e2G1:G2:V(G2)={A,B,C,D}E(G2)={e1,e2,e3,e4,e5,e6,e7}精选课件在图中,结点的相对位置不同,边的曲直、:??va??b邻接边:关联同一个结点的两条边.???环:只关联一个结点的边.??平行边::::不与任何边关联的结点.?u零图:?即此图的边的集合E=Φb?c?平凡图:仅由一个孤立结点构成的零图.|V(G)|=1,|E(G)|=0e1ve2G:????::::G是个无向图,v∈V(G),结点v所关联边数,(v).(或d(v)).deg(a)=3deg(b)=5deg(c)=4deg(d)=:令G=<V,E>是无向图,V={v1,v2,v3,…,vn},那么称:(deg(v1),deg(v2),deg(v3),…,deg(vn)):(3,5,4,2)(G)与最小度δ(G):G=<V,E>是无向图,Δ(G)=max{deg(v)|v∈G}δ(G)=min{deg(v)|v∈G}A?B?C??De1e5e7e6e3e4e2?cb?a?c?a??b?d精选课件上图中Δ(G)=5δ(G)=-:因为图中每条边关联两个结点,因此每条边给予它所关联的两个结点的度各是1,即一条边对应的度数是2,-(握手定理)每个无向图中,奇数度的结点必为偶数个.(一次集会中,与奇数个人握手的人,必是偶数个.)证明:令G=<V,E>是无向图,将V分成两个子集V1和V2,其中V1---是度数是奇数的结点集合,V2---,于是奇数度的结点数是偶数.∑deg(v)=2|E|v∈V∑deg(v)+∑deg(v)=2|E|v∈V1v∈V2∑deg(v)v∈V2∑deg(v)v∈-正那么图:一个无向简单图G中,如果Δ(G)=δ(G)=k那么称G为k-:,可能是一个图的度数序列?如果可能,?a)(1,2,3,4,5)b)(2,2,2,2,2)c)(1,2,3,2,4),有10条边,4个3度结点,其余结点的度均小于或等于2,问G中至少有多少个结点?为什么??????????????????????????)(1,2,3,4,5)b)(2,2,2,2,2)c)(1,2,3,2,4)解:a)不是,)是. c)可能不是简单图,如图::边数|E|=10,∑deg(v)=2|E|=20其中有4个3度结点,余下结点度之和为:20-3×4=8因为G是简单图,其余每个结点度数≤2,,8个结点也是足够的。例如“目〞的图形就是满足条件的例子。???????????????精选课件