《图的基本概念lly》.ppt

该【《图的基本概念lly》 】是由【相惜】上传分享，文档一共【81】页，该文档可以免费在线阅读，需要了解更多关于【《图的基本概念lly》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第8讲图的根本概念重点重要概念:简单图,度与握手定理、完全图、同构图通路、回路、图的连通性图的矩阵表示与应用欧拉图与哈密尔顿图难点同构图,割集,初级通路与简单通路区别精选课件18世纪:哥尼斯堡(Konigsiberg)七桥问题图论是近年来开展迅速而又应用广泛的一门新兴学科。它最早起源于数学游戏的难题研究。acdbadcb精选课件1859年:哈密尔顿提出环游世界19~20世纪:迷宫、棋盘上马的行走线路1852年:格色里(Guthrie)提出四色猜想精选课件在工程科学中的应用:现实世界中,许多状态都可用图来描述,例如交通运输、城市规划、电路网络、工作调配等都可以用点和边连结的图来模拟。在计算机学科中,计算机网络、操作系统数据库,数据结构等等都与图论有重要的联系。精选课件计算机科学广泛应用于运筹学,信息论,控制论,网络理论,化学生物学,物理学。原因在于这些学科的许多实际问题和理论问题可以概括为图论。第七、八、九章介绍与计算机科学关系密切的图论内容及其在实际中的应用。精选课件一、,这是不同于几何图形的另一数学结构。adcb我们不关心边的长短与形状。但边可以是有方向的,有方向的边称为有向边,没有方向的边称为无向边。精选课件称{{a,b}|a?A?b?B}为A与B的无序积,记作:A&B****惯上,无序对{a,b}改记成(a,b)有序对(a,b)均用<a,b>无序积:设A,B为二集合,=(b,a)≠<b,a>:无向图G是一个二元组<V,E>,其中(1)V是一个非空集–––顶点集V(G),每个元素为顶点或结点;(2)E是无序积V&V的可重子集(?元素可重复出现),E–––边集E(G),E中元素称为无向边。通常记:V={v1,v2,…,vn}E={e1,e2,…,em}其中:ek=(vi,vj)精选课件实际中,图的画法:用小圆圈表示V中的每一个元素,如果(vi,vj)?E,那么在顶点vi与vj之间连线段。如(1):G=<V,E>,V={v1,v2,v3,v4},E={(v1,v2),(v1,v2),(v2,v3),(v2,v3),(v3,v4),(v2,v4),(v1,v4)}v1v4v3v2e1e7e2e3e4e5e6(1)v4e1e2e3e4e5e6v1v2v3v5(2)如(2):G=<V,E>,V={v1,v2,v3,v4,v5},E={(v2,v2),(v1,v2),(v2,v3),(v1,v3),(v1,v3),(v1,v4)}精选课件有向图:有向图D是一个二元组<V,E>,其中(1)V是非空集–––顶点集V(D)(2)E是笛卡尔积V?V的可重子集,其元素为有向边实际中,画法同无向图,只是要根据E中元素的次序,由第一元素用方向线段指向第二元素。