离散数学ch省公共课一等奖全国赛课获奖课件.pptx

第五部分图论第十四章图基本概念14.1图有向图相关概念8.邻域与关联集①vV(G)(G为无向图)多重图与简单图顶点度数定理14.1设G=<V,E>为任意无向图，V={v1,v2,…,vn},|E|=m,则握手定理推论例1无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点度数均小于3，问G阶数n为几？图度数列图同构图同构实例n阶完全图与竞赛图n阶k正则图子图例2画出K4全部非同构生成子图补图14.2通路与回路几点说明通路与回路长度14.3图连通性短程线与距离无向图连通度点割集与割点点连通度与边连通度几点说明有向图连通性有向图连通性及分类扩大路径法实例扩大路径法应用二部图二部图判别法14.4图矩阵表示有向图关联矩阵（无环有向图）有向图邻接矩阵（无限制）推论设Bl=A+A2+…+Al（l1），则Bl中元素例5有向图D如图所表示，求A,A2,A3,A4，并回答诸问题：(1)D中长度为1,2,3,4通路各有多少条？其中回路分别为多少条？(2)D中长度小于或等于4通路为多少条？其中有多少条回路？定义14.27设D=<V,E>为有向图.V={v1,v2,…,vn},令第十四章习题课基本要求1．9阶无向图G中，每个顶点度数不是5就是6.证实G中最少有5个6度顶点或最少有6个5度顶点.2．数组2,2,2,2,3,3能简单图化吗？若能，画出尽可能多非同构图来.用扩大路径法证实.情况一：+.证实D中存在长度+1圈.设=v0v1…vl为极大路径，则l(为何?).因为d(v0)，所以在上存在(1)D中有几个非同构圈？(2)D中有几个非圈非同构简单回路？(3)D是哪类连通图?(4)D中v1到v4长度为1,2,3,4通路各多少条？其中几条是非初级简单通路？(5)D中v1到v1长度为1,2,3,4回路各多少条？讨论它们类型.(6)D中长度为4通路（不含回路）有多少条？(7)D中长度为4回路有多少条？(8)D中长度4通路有多少条？其中有几条是回路？(9)写出D可达矩阵.解答(4)v1到v4长度为1,2,3,4通路数分别为0,0,2,2.其中只有长度为4两条是非初级简单通路（定义意义下），见下列图所表示.解答