离散数学-教案 第5章5.1-5.2 无向图及有向图

课堂教学设计16章节（专题）第5章图计划学时2课题（内容）5.1无向图及有向图教育教学目的1.掌握无向图、有向图的概念2.掌握结点的度的定义和相关性质3.理解图的同构4.思政目标：结合图论在实际应用中的案例，如交通网络规划、社交网络分析等，引导学生思考如何将所学知识应用于社会服务，培养学生的社会责任感。鼓励学生通过构建无向图和有向图的模型来解决实际问题，培养他们的创新思维和实践能力。引导学生探索图论领域的前沿技术和应用，激发他们的探索精神和创新意识。教学重点及难点1.重点：掌握并理解图的定义和相关术语结点的度的定义和相关性质2.难点：结点的度的定义和相关性质教学方法及手段1.讲授法2.互动式教学3.多媒体辅助教学教学互动环节设计1.交叉学科的联系导入新课（通过生活中的例子（如交通网络、社交网络等）引入无向图和有向图的概念，让学生理解这些图论知识在现实生活中的应用。）2.启发式提问引发课堂讨论（有向图，无向图）课后总结与反思第5章图5.1无向图及有向图无向图多重集合:元素可以重复出现的集合无序积:A＆B={(x,y)|x∈A∧y∈B}定义无向图G=<V,E>,其中(1)顶点集V是非空有穷集合,其元素称为顶点(2)边集E为V＆V的多重子集，其元素称为无向边，简称边.例如,G=<V,E>,其中V={v1,v2,…,v6},E={(v2,v2),(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v4,v5),(v4,v5),(v5,v6)}有向图定义有向图D=<V,E>,其中(1)顶点集V是非空有穷集合,其元素称为顶点(2)边集E为VxV的多重子集，其元素称为有向边，简称边.D的基图:用无向边代替有向边如D=<V,E>,其中V={v1,v2,v3,v4}E={<v1,v1>,<v1,v4>,<v2,v1>,<v3,v1>,<v3,v2>,<v3,v4>,<v4,v3>}图的数学定义与图形表示,在同构意义下一一对应通常用G表示无向图,D表示有向图,也常用G泛指无向图和有向图.V(G),E(G),V(D),E(D):G和D的顶点集,边集.n阶图:n个顶点的图;零图:E=;平凡图:1阶零图;空图:V=顶点和边的关联与相邻定义设e=(u,v)是无向图G=<V,E>的一条边,称u,v为e的端点,e与u(v)关联.若uv,则称e与u(v)的关联次数为1;若u=v,则称e为环,此时称e与u的关联次数为2;若w不是e端点,则称e与w的关联次数为0.无边关联的顶点称作孤立点.定义设无向图G=<V,E>,u,vV,e,eE,若(u,v)E,则称u,v相邻;若e,e至少有一个公共端点,则称e,e相邻.对有向图有类似定义.设e=u,v是有向图的一条边,又称u是e的始点,v是e的终点,u邻接到v,v邻接于u.顶点的度数设G=<V,E>为无向图,vV,v的度数(度)d(v):v作为边的端点次数之和悬挂顶点:度数为1的顶点悬挂边:与悬挂顶点关联的边G的最大度(G)=max{d(v)|vV}G的最小度(G)=min{d(v)|vV}例如d(v5)=3,d(v2)=4,d(v1)=4,(G)=4,(G)=1,v4是悬挂顶点,e7是悬挂边,e1是环设D=<V,E>为有向图,vV,v的出度d+(v):v作为边的始点次数之和v的入度d(v):v作为边的终点次数之和v的度数(度)d(v):v作为边的端点次数之和d(v)=d+(v)+d-(v)握手定理定理任意无向图和有向图的所有顶点度数之和都等于边数的2倍,并且有向图的所有顶点入度之和等于出度之和等于边数.推论任意无向图和有向图，度数为奇数的顶点个数必为偶数.例1(3,3,3,4),(2,3,4,6,8)能成为图的度数列吗?解不可能.它们都有奇数个奇数.例2已知图G有10条边,4个3度顶点,其余顶点的度数均小于等于2,问G至少有多少个顶点?解设G有n个顶点.由握手定理,43+2(n-4)210解得n8图的度数列多重图与简单图定义(1)在无向图中,如果有2条或2条以上的边关联同一对顶点,则称这些边为平行边,平行边的条数称为重数.(2)在有向图中,如果有2条或2条以上的边具有相同的始点和终点,则称这些边为有向平行边,简称平行边,平行边的条数称为重数.(3)含平行边的图称为多重图.(4)既无平行边也无环的图称为简单图.完全图n阶无向完全图Kn:每个顶点都与其余顶点相邻的n阶无向简单图.简单性质:边数m=n(n-1)/2,==n-1n阶有向完全图:每对顶点之间均有两条方向相反的有向边的n阶有向简单图.简单性质:边数m=n(n-1),==2(n-1),+=+=-=-=n-1子图定义设G=<V,E>,G=<V,E>是两个图(1)若VV且EE,则称G为G的子图,G为G的母图,记作GG(2)若GG且V=V，则称G为G的生成子图(3)若VV或EE，称G为G的真子图(4)设VV且V,以V为顶点集,以两端点都在V中的所有边为边集的G的子图称作V的导出子图，记作G[V](5)设EE且E,以E为边集,以E中边关联的所有顶点为顶点集的G的子图称作E的导出子图,记作G[E]导出子图实例补图对K4的所有子图,指出互为补图的每一对子图,并指出哪些是自补图.图的同构课堂教学设计17章节（专题）第5章图的基本概念计划学时2课题（内容）5.2通路、回路和图的连通性教育教学目的1.掌握通路与回路的概念2.掌握无向图及有向图的联通性3.理解点割集及边割集概念4.思政目标：结合通路、回路和图的连通性在交通网络规划、网络通信、物流运输等领域的应用案例，引导学生认识到数学在社会发展中的重要作用。通过介绍中国在这些领域取得的成就和面临的挑战，激发学生的社会责任感和家国情怀，鼓励他们努力学习，为国家的科技进步和社会发展做出贡献。教学重点及难点1.重点：图连通性的判断、连通分支的计算2.难点：单向连通图的判断连通分支的计算教学方法及手段1.讲授法2.分组讨论3.多媒体辅助教学教学互动环节设计1.课程回顾导入新课（平凡图、等价关系）2.启发式提问引发课堂讨论（铁路交通路线）课后总结与反思5.2通路、回路和图的连通性通路与回路定义给定图G=<V,E>（无向或有向的），G中顶点与边的交替序列=v0e1v1e2…elvl，(1)若i(1il),vi1,vi是ei的端点(对于有向图,要求vi1是始点,vi是终点),则称为通路,v0是通路的起点,vl是通路的终点,l为通路的长度.又若v0=vl，则称为回路.(2)若通路(回路)中所有顶点(对于回路,除v0=vl)各异，则称为初级通路(初级回路).初级通路又称作路径,初级回路又称作圈.(3)若通路(回路)中所有边各异,则称为简单通路(简单回路),否则称为复杂通路(复杂回路).通路与回路实例说明:表示方法①用顶点和边的交替序列(定义),如=v0e1v1e2…elvl②用边的序列,如=e1e2…el③简单图中,用顶点的序列,如=v0v1…vl④非简单图中,可用混合表示法,如=v0v1e2v2e5v3v4v5环是长度为1的圈,两条平行边构成长度为2的圈.在无向简单图中,所有圈的长度3;在有向简单图中,所有圈的长度2.在两种意义下计算圈的个数定义意义下在无向图中,一个长度为l(l≥3)的圈看作2l个不同的圈.如v0v1v2v0,v1v2v0v1,v2v0v1v2,v0v2v1v0,v1v0v2v1,v2v1v0v2看作6个不同的圈.在有向图中,一个长度为l(l≥3)的圈看作l个不同的圈.②同构意义下所有长度相同的圈都是同构的,因而是1个圈.定理在n阶图G中，若从顶点u到v（u≠v）存在通路，则从u到v存在长度小于等于n-1的通路.推论在n阶图G中，若从顶点u到v（u≠v）存在通路，则从u到v存在长度小于等于n-1的初级通路.定理在一个n阶图G中，若存在v到自身的回路，则一定存在v到自身长度小于等于n的回路.推论在一个n阶图G中，若存在v到自身的简单回路，则存在v到自身长度小于等于n的初级回路.无向图的连通性设无向图G=<V,E>,u与v连通:若u与v之间有通路.规定u与自身总连通.连通关系R={<u,v>|u,vV且uv}是V上的等价关系连通图:任意两点都连通的图.平凡图是连通图.连通分支:V关于连通关系R的等价类的导出子图设V/R={V1,V2,…,Vk},G[V1],G[V2],…,G[Vk]是G的连通分支,其个数记作p(G)=k.G是连通图p(G)=1点割集记Gv:从G中删除v及关联的边GV:从G中删除V中所有的顶点及关联的边Ge:从G中删除eGE:从G中删除E中所有边定义设无向图G=<V,E>,VV,若p(GV)>p(G)且VV,p(GV)=p(G),则称V为G的点割集.若{v}为点割集,则称v为割点.边割集定义设无向图G=<V,E>,EE,若p(GE)>p(G)且EE,p(GE)=p(G),则称E为G的边割集.若{e}为边割集,则称e为割边或桥.在上一页的图中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集，e8是桥，{e7,e9,e5,e6}不是边割集说明：Kn无点割集n阶零图既无点割集，也无边割集.若G连通，E为边割集，则p(GE)=2；若G连通，V为点割集，则p(GV)2例在图中，{v1,v