20210118第十五章复习

第十五章 欧拉图与哈密顿图

欧拉图

通过图中所有便一次且仅一次形变所有顶点的通路称作欧拉通路
通过图中所有边一次且仅一次行遍所有顶点的回路称作欧拉回路
具有欧拉回路的图称作欧拉图，具有欧拉通路而无欧拉回路的图称作半欧拉图。

无向图是欧拉图当且仅当 G 是联通图且没有极度顶点
无向图是半欧拉图当且仅当 G 是联通的且卡有两个极度顶点
有向图是欧拉图当且仅当 D 是强连通的，且每个顶点的入度等于出度
有向图是半欧拉图当且仅当 D 是单项联通的且恰有两个极度顶点，其中一个顶点入度笔触都大一，零一个顶点出度比入度大一。

哈密顿图

经过图中所有顶点一次且仅一次的通路称作哈密顿通路，
经过途中所有顶点一次且仅一次的回路称作哈密顿回路
具有哈密顿回路的图称作哈密顿图
具有哈密顿通路，但无回路的图称作班哈密顿图