电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

第四次辅导-欢迎访问安徽广播电视大学网站!VIP免费

第四次辅导-欢迎访问安徽广播电视大学网站!_第1页
1/16
第四次辅导-欢迎访问安徽广播电视大学网站!_第2页
2/16
第四次辅导-欢迎访问安徽广播电视大学网站!_第3页
3/16
第1页共16页编号:时间:2021年x月x日书山有路勤为径,学海无涯苦作舟页码:第1页共16页《计算机数学基础(1)》第四单元辅导本单元重点:欧拉图和哈密顿图、平面图和树的基本概念.代数运算及性质,群的概念,交换群和循环群.一、重点内容1.欧拉图欧拉通路(回路)与欧拉图通过图G的每条边一次且仅一次,而且走遍每个结点的通路(回路),就是欧拉通路(回路).存在欧拉回路的图就是欧拉图.欧拉回路要求边不能重复,结点可以重复.笔不离开纸,不重复地走完所有的边,且走过所有结点,就是所谓的一笔画.欧拉图或通路的判定(1)无向连通图G是欧拉图G不含奇数度结点(G的所有结点度数为偶数):(定理1)(2)非平凡连通图G含有欧拉通路G最多有两个奇数度的结点;(定理1的推论)(3)连通有向图D含有有向欧拉回路(即欧拉图)D中每个结点的入度=出度连通有向图D含有有向欧拉通路D中除两个结点外,其余每个结点的入度=出度,且此两点满足deg-(u)-deg+(v)=1.(定理2)2.哈密顿图哈密顿通路(回路)与哈密顿图通过图G的每个结点一次,且仅一次的通路(回路),就是哈密顿通路(回路).存在哈密顿回路的图就是哈密顿图.判断哈密顿图是较为困难的.哈密顿图的充分条件和必要条件(1)在无向简单图G=中V3,任意不同结点u,v∈G,deg(u)+deg(v)≥|V|,则G是哈密顿图.(充分条件,定理4)(2)有向完全图D=,若|V|≥3,则图D是哈密顿图.(充分条件,定理5推论)(3)设无向图G=,V1V,则P(G-V1)V1(必要条件,定理3)若此条件不满足,即V1V,使得P(G-V!)>V1,则G一定不是哈密顿图(非哈密顿图的充分条件).3.平面图平面图一个图能画在平面上,除结点之外,再没有边与边相交.面、边界和面的次数由连通平面图G的边围成的其内部不含G的结点和边的区域是面,常用r表示.围成面的各边组成的回路是边界.边界回路的长度是面的次数,记作deg(r).重要结论(1)平面图G=,|V|=v,|E|=e,则∑i=1rdeg(ri)=2e(所有面的次数之和=边的2倍)(定理6).(2)欧拉公式:平面图G=,|V|=v,|E|=e,面数为r,则v−e+r=2(结点数与面数之和=边数+2)(定理7)(3)平面图G=,|V|=v,|E|=e,v若≥3,则e≤3v−6(定理8)第2页共16页第1页共16页v4v5EFAv2v3BCv1D(a)(b)图6-1v1v1dv4v2v5fhagecv3v4v2bv3D1D2图6-2编号:时间:2021年x月x日书山有路勤为径,学海无涯苦作舟页码:第2页共16页判定条件:图G是平面图的充分必要条件是G不含与K3,3或K5在2度结点内同构的子图.4.树树连通无回路的无向图.树的判别图T=,|V|=n,|E|=m,T是树的充分必要条件是(六个等价定义)(定理14):(1)T是无回路的连通图;(2)图T无回路且m=n-1;(3)图T连通且m=n-1(4)图T无回路,若增加一条边,就得到一条且仅一条回路;(5)图T连通,若删去任一边,G则不连通;(6)图T的每一对结点之间有一条且仅有一条通路.生成树图G的生成子图是树,该树就是生成树.权与带权图n个结点的连通图G,每边指定一正数,称为权,每边带权的图称为带权图.G的生成树T的所有边的权之和是生成树T的权,记作W(T).最小生成树带权最小的生成树.有向树有向图删去边的方向为树,该有向图就是有向树.根树与树根非平凡有向树,恰有一个结点的入度为0(该结点为树根),其余结点的入度为1,该树为根树.每个结点的出度小于或等于2的根树为二元树(二叉树);每个结点的出度等于0或2的根树为二元完全树(二叉完全树);每个结点的出度等于2的根树称为正则二元树(正则二叉树).哈夫曼树用哈夫曼算法得到的最优二叉树.4.有关树的求法生成树的破圈法和避圈法求法;最小生成树的克鲁斯克尔求法;哈夫曼树的哈夫曼求法.二、实例例6.1判别图6-1的两幅图是否可以一笔画出?解在图6-1(a)中,deg(v1)=deg(v2)=deg(v3)=3有两个以上的结点的度为3.故在(a)中不存在欧拉通路,不能一笔画出.在图6-1(b)中,deg(A)=2,deg(B)=deg(C)=deg(D)=4,deg(E)=deg(F)=3只有两个奇数度的结点,所以存在欧拉通路,可以一笔画出.一条欧拉通路,如EDBEFCABCDF.例6.2判定图6-2中,两个图是否有欧拉回路?若有请把欧拉回路写出来.解在图D1中,v1点的出度为2,入度为0...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

第四次辅导-欢迎访问安徽广播电视大学网站!

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部