资源预览内容
第1页 / 共32页
第2页 / 共32页
第3页 / 共32页
第4页 / 共32页
第5页 / 共32页
第6页 / 共32页
第7页 / 共32页
第8页 / 共32页
第9页 / 共32页
第10页 / 共32页
亲,该文档总共32页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
,离散数学第七章 图 论,7-1 图的基本概念,7-2 路与回路,7-3 图的矩阵表示,7-4 欧拉图与哈密尔顿图,7-5 平面图,7-6 对偶图与着色,7-7 树与生成树,7-8 根树及其应用,绪论,图论的诞生哥尼斯堡七桥问题,从任意一点出发,经过每座桥恰好一次,再回到原点。,1736年,欧拉(Euler)解决了该问题图论诞生。,几个有名的图论问题,四色猜想 莫比乌斯( Mbius )于1840年提出:对地图上的每个国家着色,使得任意相邻的两个国家着不同的颜色,猜想:只需要四种颜。阿佩尔和哈肯(Appel,Haken)于1976借助计算机花费1200小时证明了该猜想。,中国邮递员问题,管梅谷与1960年提出: 一个邮递员,每次送信必须从邮局出发,走遍他所投递的区域内的所有街道,最终回到邮局。问:怎样使他所走的路最短。哥尼斯堡七桥问题:每条边走恰好一次;中国邮递员问题:每条边可以走多次。,哈密尔顿图,戏) 求解 问题 1859年爱尔兰数学家威廉哈密尔顿(Sir William Hamilton)发明了一个小游戏玩具:一个木刻的正十二面体,每面系正五角形,三面交于一角,共有20个角,每角标有世界上一个重要城市。哈密尔顿提出一个问题:要求沿正十二面体的边寻找一条路通过20个城市,而每个城市只通过一次,最后返回原地。哈密尔顿将此问题称为周游世界问题。游抽象为图论问题哈密尔顿给出了肯定回答,该问题的解是存在的,哈密尔顿回路(圈)哈密尔顿图,运筹学、计算机科学和编码理论中的很多问题都可以化为哈密尔顿图问题,旅行售货员问题,给出城市之间的距离,一位售货员从某一城市出发,经过每个城市恰好一次,然后回到出发的城市,要求他所走的路经最短。 美国数学家威特涅与1934年在普林斯顿的一个讨论班上提出。该问题在理论和应用上都很有价值,迄今有很多论文研究该问题。,图论及其在计算机科学中的应用例子,图论在许多领域,诸如,计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用。 在计算机科学领域,如数据结构、语言、算法、数据库、操作系统、人工智能、网络理论、开关理论等方面,图论扮演着重要的角色。如: 数据结构中的图、树 数据库中的网状模型 计算机网络中的环网络、星形网络等 算法设计与分析、人工智能 并行计算机中的多处理器互连网络(Multiprocessor Interconnection Network) 无线传感器网络(Wireless Sensor Network) ,多处理器互连网络,一个多处理器互连网络可用一个图G=(V,E)表示,其中V中的每个顶点v表示一个处理器,E中的每条边表示处理器之间的链路(Hard-link)。 应用:并行计算机中若干个处理器连接的方式。 例:n维超立方体Q_n=(V,E): V中每个顶点表示为一个长度为n的二进制串,E中两个顶点之间有一条边当且仅当它们只有一位不同。顶点个数2n,边数:n2n-1。超立方体性并行机:CM-2,nCUBE,IPSC-860,SGI Origin 2000。,IBM的蓝色基因/L(Bluegene/L):65536个处理器,Torus网络结构运算速度:2005年IBM的蓝色基因以每秒钟计算280万亿次浮点运算;2007年每秒钟计算一千万亿次浮点运算每秒蝉联冠军宝座(Roadrunner)。 超级计算机的应用:石油勘探、天气、天文、生物等方面。,第七章 图论-绪论,图论起源于智力游戏的难题研究,如哥尼斯堡七桥问题、迷宫问题、匿门博奕问题、四色猜想问题、汉密尔顿(环游世界)、棋盘上马的行走线路问题等。,图论的第一篇论文,1736年欧拉发表的,阐述了解决哥尼斯堡七桥问题的思想。 欧拉享有“图论之父”之称。,1847年克希霍夫利用图论分析电路网络中的电流问题。,图论起源,图论应用于工程技术问题的首篇论文,7-1 图的基本概念,一、图的定义,三、几个基本概念,四、结点度数的 几个基本定理,五、子图与补图,六、图的同构,第七章 图 论,7-1 图的基本概念-定义,图的定义(定义7-1.1)一个图是一个三元组,其中V(G)是一个非空的 结点集合, E(G)是边集合, G 是从边集合E到结点无序偶(或有序偶)集合上的函数。,例1 无向图,例2 有向图,例3 混合图,若把图中的边ei看作总是与两个结点关联,那么一个图亦可 记为G=,其中V是非空结点集,E是连接结点的边集。,7-1 图的基本概念目录,若边ei与结点无序偶(vj,vk)相关联,则称该边为无向边。,若边ei与结点有序偶相关联,则称该边为有向边,其中yj为起点,yk为终点。,例1 G=,其中V(G)=a,b,c,d, E(G)=e1,e2,e3,e4,e5,e6, G(e1)=(a,b), G(e2)=(a,c), G(e3)=(b,d), G(e4)=(b,c), G(e5)=(d,c), G(e6)=(a,d)。,返回,无向图-图中每一条边为无向边。,7-1 图的基本概念-定义,例2 G=,其中V(G)=a,b,c,d, E(G)=e1,e2,e3,e4,e5,e6, G(e1)=, G(e2)=,G(e3)=, G(e4)=, G(e5)=, G(e6)=。,返回,有向图-图中每一条边为有向边。 (一般地: ),7-1 图的基本概念-定义,返回,混合图-图中一些边为有向边,一些边为无向边。 例 3,7-1 图的基本概念-定义,7-1 图的基本概念-几个基本概念,边与两个结点关联,邻接点,无向边 有向边 平行边,邻接边,环(或自回路),简单图 多重图 完全图,孤立结点 零图 平凡图,结点的度数,7-1 图的基本概念,若G(e)=(a,b),或G(e) =,则称边e与两个结点a,b关联。例如,e1关联于结点a,b,e2关联于结点v1,v2。,邻接点-由一条有向(或无向)边关联的结点称为邻接点。如图,a,b互为邻接点,v1与v2邻接。,环或自回路-关联于同一结点的一条边。,孤立结点-在一个图中不与任何结点相邻接的结点。,零图仅由孤立结点组成的图称为零图。 平凡图仅由一个孤立结点构成的图称为平凡图。,几个基本概念,7-1 图的基本概念-几个基本概念,邻接边-关联于同一结点的多条边。例如,e1,e2,e6互为邻接边。,平行边-连接于同一对结点间的多条边称为平行边。如果是有向边要求方向一致。,多重图-含有平行边的图称为多重图。,简单图不含平行边和环的图。,a,b,c,几个基本概念,7-1 图的基本概念-几个基本概念,完全图(无向图)-在简单图中,若每一对不同结点间都有边相连,则称该图为完全图。有n个结点的无向完全图记作Kn 。如果在Kn中,给每条边任意确定一个方向,就称该图 为n个结点的有向完全图。,7-1 图的基本概念-几个基本概念,几个基概念,完全图的性质(定理7-1.4)n个结点的无向完全图Kn的边数为:n(n-1)/2。 定理7-1.4证明:,结点的度数(定义7-1.2 )在图G=,与结点v关联的边数,称作是该 结点的度数,记作deg(v)。 图G=的最大度(G)=maxdeg(v)|vV(G),图 G=的最小度(G)=mindeg(v)|vV(G)。,有向图中结点的度数(定义7-1.3 )在有向图中,射入一个结点的边数称为该结点的入度,由一个结点射出的边数称为该结点的出度。结点的出度与入度之和就是该结点的度数。,7-1 图的基本概念-几个基本概念,定理7-1.1 (握手定理) 每个图中,所有结点度数的总和等于边数的两倍,即deg (v) = 2|E| vV 证明:因为每条边必关联两个结点,而一条边给于 关联的每个结点的度数为1。因此在一个图中,结 点度数的度数的总和等于边数的两倍。,返回几个定理,7-1 图的基本概念-几个定理,定理7-1.2 在任何图中,度数为奇数的结点必定为偶数个。 证明:设V1和V2分别是G中奇数和偶数度数的结点集,则由定 理7-1.1,有deg(v) +deg(v) = deg(v) = 2|E| vV1 vV2 vV 由于deg(v) 是偶数之和,必为偶数,而2|E| 是偶数,vV2 故得deg(v)是偶数,即| V1 | 是偶数。vV1,返回几个定理,7-1 图的基本概念-几个定理,定理7-1.3 在任何有向图中,所有结点的入度之和等于所 有结点的出度之和。 证明:因为每一条有向边必对应一个入度和一个出度,若 一个结点具有一个入度或出度,则必关联一条有向边。 所以,有向图中各结点入度之和等于边数,各结点出度 之和也等于边数,因此,任何有向图中,入度之和等于 出度之和。,返回几个定理,7-1 图的基本概念-几个定理,定理7-1.4 n个结点的无向完全图Kn的边数为 n(n-1)/2 。 证明:在Kn中,任意两个结点间都有边相连,n个结点中 任取两点的组合数为:Cn2= n(n-1)/2 故Kn的边数为:|E|= n(n-1)/2 。,返回,7-1 图的基本概念-几个定理,子图 (定义7-1.7 )设图G=,若有一个图G=满足VV且EE, 则称G为G的子图。 例如: 下图中(b),(c)都是(a)的子图。,7-1 图的基本概念-子图,返回,图G相对于完全图的补图 (定义7-1.6 )给定一个图G,由G中所有结点和所有能使G成为完全 图的添加边组成的图,称为G的相对于完全图的补图,或 简称为G的补图,记作G。 例如:,子图G的相对于图G的补图(定义7-1.8 )设G=是G=的一个子图,若给定另外一个图 G”=使得E”=E-E,且V”中仅包含E”的边所关联的结点,则称G”是子图G的相对于图G的补图。例如:,7-1 图的基本概念-补图,返回7-1,图G相对于完全图的补图 (定义7-1.6 ) 给定一个图G,由G中所有结点和所有能使G称为完全 图的添加边组成的图,称为G的相对于完全图的补图,或 简称为G的补图,记作G。 例如:,7-1 图的基本概念-补图,返回,子图G的相对于图G的补图 (定义7-1.8 )设G= 是图G=的子 图,若给定另外一个图 G”=使得E”=E-E,且V”中仅包含E”的边所关联的结点,则称G”是子图G的相对于图G的补图。 例如:图(c)是图(b)相对于图(a)的补图。图(b)不是 图(c)相对于图(a)的补图。,7-1 图的基本概念-补图,返回,图的同构(定义7-1.9)设图G=及图G=,如果存在双射 g: vi vi,使得e=(vi,vj)(或)是G的一条边当且仅当 e=(g(vi),g(vj) (或)是G的一条边,则称G与G同构,记作GG。,7-1 图的基本概念-图的同构,G与G同构的充要条件: 两个图的结点和边分别存在一一对应,且保持关联关系。,两个图同构的必要条件: 1、结点数目相同; 2、边数相等; 3、度数相同的结点数相等。,例如:,7-1 图的基本概念,7-1 图的基本概念-图的同构,图(a)与(b)是同构的。图 (c)与(d)是同构的。,同构的定义,导出子图:设G=(V,E)是一个图,E是E的子集。以E为边集,E中的边所关联的结点的全体为结点集所得到的G的子图,称为由E导出的G的子图,记为GE 。 设V是V的子集,以V为结点集,端点均在V中的边的全体为边集所得到的G的子图,称为由V导出的G的子图,记为GV 。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号