几种特殊的图
几种特殊的图
11.1欧拉图历史背景：哥尼斯堡七桥问题BBAD2
2 11.1 欧拉图 历史背景：哥尼斯堡七桥问题
欧拉图定义定义11.1图（无向图或有向图）中所有边恰好通过一次且经过所有顶点的通路称为欧拉通路图中所有边恰好通过一次且经过所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图具有欧拉通路而无欧拉回路的图称为半欧拉图。说明：规定平凡图为欧拉图环不影响图的欧拉性3
3 欧拉图定义 定义11.1 • 图(无向图或有向图)中所有边恰好通过一次且经过所有顶点的通 路称为欧拉通路. • 图中所有边恰好通过一次且经过所有顶点的回路称为欧拉回路． • 具有欧拉回路的图称为欧拉图. • 具有欧拉通路而无欧拉回路的图称为半欧拉图． 说明： 规定平凡图为欧拉图. 环不影响图的欧拉性
欧拉图实例e6eteteieese2e4e2e4ee4eseses不是半欧拉图欧拉图eieieiese2e2e4ese2e4e:eses不是欧拉图半欧拉图4
4 欧拉图实例 欧拉图 半欧拉图 不是 欧拉图 半欧拉图 不是
欧拉图的判别法定理11.1（1）无向图G是欧拉图当且仅当G是连通的且没有奇度项点：(2）无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点.5
5 欧拉图的判别法 定理11.1 (1) 无向图G是欧拉图当且仅当G是连通的且没有奇度顶点． (2) 无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度 顶点．