欧拉图与哈密顿图欧拉图与哈密顿图 欧欧 拉拉 图图 一欧拉通路、欧拉回路、欧拉图、半一欧拉通路、欧拉回路、欧拉图、半 欧拉图的定义欧拉图的定义 定义定义 通过图（无向图或有向图）中所通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图路称为欧拉回路。具有欧拉回路的图称为欧拉图，具有欧拉通路而无称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。欧拉回路的图称为半欧拉图。从定义不难看出，欧拉通路是图中经过所有边的简单的生成通路（经过所有顶点的通路称为生成通路），类似地，欧拉回路是经过所有边的简单的生成回路。在这里做个规定，即平凡图是欧拉图。图 在图所示各图中，为（）中的欧拉回路，所以（）图为欧拉图。为（）中的一条欧拉通路，但图中不存在欧拉回路，所以（）为半欧拉图。（）中既没有欧拉回路，也没有欧拉通路，所以（）不是欧拉图，也不是半欧拉图。为（）图中的欧拉回路，所以（）图为欧拉图。（），（）图
