10.5欧拉路径和欧拉回路(Euler Paths and Circuits)
引入:七桥问题
"一笔画"--》针对边而言
欧拉图(Eulerian graph)
- 图G的欧拉回路(Euler circuit)指的是遍历G中每一条边的简单回路(simple circuit), 这样的轨迹称为欧拉环游(Euler tour)
- 图G的欧拉路径(Euler path)指的是遍历G中每一条边的简单路径(simple path), 这样的轨迹称为欧拉轨迹(Euler trail)
- 有欧拉回路的图称为欧拉图，无欧拉回路但是有欧拉路径的图称为半欧拉图
定理1：
连通图G是欧拉图，当且仅当，G是连通的，并且没有度为奇数(odd)的顶点
定理2：
连通图G是存在从a到b的欧拉路径，当且仅当，G是连通的，并且除a和b(a≠b)的度为奇数(odd)之外，没有度为奇数(odd)的顶点
定理3：
有向连通图G是欧拉图，当且仅当，G是连通的，并且G的每个顶点的入度＝出度
定理4：
有向连通图G含有欧拉通路，当且仅当，G是连通的，并且G中除两个顶点(节点不相等)外，其余每个顶点的入度=出度，且此两点满足(deg^-(u)-deg^+(v)=±1)
证明均略
哈密顿路径与回路(Hamilton Paths and Circuits)
哈密顿图(Hamiltonian Graph)
- 图G的哈密顿回路(Hamiltonian circuit)指的是遍历G中每一个点且只遍历一次的回路, 这样的轨迹称为哈密顿环游(Hamiltonian tour)
- 图G的哈密顿路径(Hamiltonian path)指的是遍历G中每一个点且只遍历一次的路径, 这样的轨迹称为哈密顿轨迹(Hamiltonian trail)
- 有哈密顿回路的图称为哈密顿图，无哈密顿回路但是有哈密顿路径的图称为半哈密顿图
遗憾的是，现在还没有快速判别一个图是否为哈密顿图的方法
记忆轮(memory wheel)
具有(2^n)的记忆轮能存储n位二进制的所有信息；且其和相应的哈密顿图是一一对应的
当然，相应转化后的欧拉图也具有一一对应关系，且更任意找
一些哈密顿图判定的充分条件
定理1：
简单图G的最小度数的顶点度数≥n/2
定理2：
简单图G的任意一对相邻点的度数和≥n
证明均略