《计算机数学基础(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=中V3,任意不一样结点u,v∈G,deg(u)+deg(v)≥|V|,则 G是哈密顿图.(充足条件，定理 4)(2) 有向完全图 D＝, 若|V|≥3，则图 D 是哈密顿图. (充足条件，定理 5 推论)(3) 设无向图 G=,V1V，则 P(G－V1)V1(必要条件，定理 3)若此条件不满足，即V1V，使得 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≤3 v−6 (定理 8) 判定条件：图 G 是平面图的充足必要条件是 G 不含与 K3，3或 K5在 2 度结点内同构的子图. v4 v5 E F Av2 v3 B C v1...
