该【图论-图的基本概念课件 】是由【rdwiirh】上传分享，文档一共【25】页，该文档可以免费在线阅读，需要了解更多关于【图论-图的基本概念课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。图论-图的基本概念教师:孙继荣电话:87768609Email:sunjr@图论-图的基本概念教师:孙继荣1图论-图的基本概念教学要求理解图的概念:结点、边、有向图,无向图、图的同构、简单图、完全图、结点的度数、子图、边的重数和平行边等理解握手定理了解通路与回路概念:通路(简单通路、初级通路和复杂通路),回路(简单回路、初级回路和复杂回路),会求通路和回路的长度了解无向图的连通性,会求无向图的连通分支。了解点割集、割点、边割集、割边、点连通度、边连通度等概念了解有向图的强连通强性;会判别其类型了解(有向图、无向图)关联矩阵、(无向图)相邻矩阵和(有向图)邻接矩阵的概念,掌握构造方法及其应用。知道带权图、最短通路概念,知道关键路径概念计算机数学基础-孙继荣图论-图的基本概念教学要求计算机数学基础-孙继荣2图论-图的基本概念学****内容:图的概念?(图的表示,有向图、无向图、度、同构)图的矩阵表示(邻接矩阵,关联矩阵)计算机数学基础-孙继荣图论-图的基本概念学****内容:计算机数学基础-孙继荣3图论--孙继荣图论-图的基本概念本章重点计算机数学基础-孙继荣4图论-图的基本概念图的基本概念图是指某些具体的事物以及这些事物之间的联系图是一个有序对<V,E>,V是结点集,E是边集,当?V?,?E?有限时,<V,E>称为有限图;,与无序结点(v,u)相关联的边有向边,与有序结点<v,u>,每条边都是无向边的图,记作G=<V,E>;每条边都是有向边的图,记作D=<V,E>.混合图,既有有向边,-孙继荣图论-图的基本概念图的基本概念计算机数学基础-孙继荣5图论-图的基本概念图的基本概念平凡图,仅有一个结点的图;零图(空图):边集为空集的图<V,?>,(环),,联结相同两个结点的多于1条的无向边;有向平行边,,-孙继荣图论-图的基本概念图的基本概念计算机数学基础-孙继荣6图论-图的基本概念图的基本概念在无向图G=<V,E>中,与结点v(?V)关联的边数,即为结点度数deg(v)或d(v).;有向图G=<V,E>中,,以结点v为始点的变的条数为该点的出度,记作deg+(v);以结点v为终点的边为该点的入度,记作deg-(v);,?(G)=max{d(v)?v?V};最小度数,?(G)=min{d(v)?v?V}计算机数学基础-孙继荣图论-图的基本概念图的基本概念计算机数学基础-孙继荣7图论-图的基本概念1图的基本概念有n个结点的且每对结点都有边相连无向简单图,;有n个结点的且每对结点之间都有两条方向相反的边相关连的有向简单图为有向完全图,.此时有设G=<V,E>,V,E的子集V?,E?构成的图G?=<V?,E?>是图G的子图;若G??G且G??G,(V??V或E??E),G?,设图G=<V,E>,若E??E,则图<V,E?>是<V,E>,-孙继荣图论-图的基本概念1图的基本概念计算机数学基础-孙继荣8图论-图的基本概念图的基本概念补图?G=<V,E?>,设G=<V,E>,以V为结点集,以使G成为完全图所添加的边为边集E?的图,就是图G的补图?G,即<V,E?E?>是完全图,其中E?E?=?.图的同构,设G1=<V1,E1>和G2=<V2,E2>,存在双射f:V1?V2,?(vi,vj)?E1,当且仅当(f(vi),f(vj))?E2,且(vi,vj)与(f(vi),f(vj))≌:建立两个图的对应关系,:①结点数相同;②边数相同;③-孙继荣图论-图的基本概念图的基本概念计算机数学基础-孙继荣9图论-图的基本概念图的基本概念握手定理:结点度数之和为边数的两倍设G=<V,E>,有在有向图图D=<V,E>中,,则这两个节点相连通。计算机数学基础-孙继荣图论-图的基本概念图的基本概念计算机数学基础-孙继荣10
图论-图的基本概念课件 来自淘豆网www.taodocs.com转载请标明出处.}