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

第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一定不是哈密顿图(非哈密顿图的充分条件)

平面图平面图一个图能画在平面上，除结点之外，再没有边与边相交

面、边界和面的次数由连通平面图G的边围成的其内部不含G的结点和