计计算算机机科科学学学学院院 刘刘 芳芳2022/12/171第15章 欧拉图和哈密顿图 15.1 欧拉图欧拉图15.2 哈密尔顿图哈密尔顿图计计算算机机科科学学学学院院 刘刘 芳芳2022/12/17215.1 欧拉图15.1.1 问题引入问题引入15.1.2 欧拉图欧拉图15.1.3 欧拉图的判定定理欧拉图的判定定理15.1.4 中国邮路问题中国邮路问题计计算算机机科科学学学学院院 刘刘 芳芳2022/12/17315.1.1 问题引入哥尼斯堡七桥问题哥尼斯堡七桥问题Seven bridges of Knigsberg problem问题分析问题分析：ACBD计计算算机机科科学学学学院院 刘刘 芳芳2022/12/17415.1.2 欧拉图定义定义15.1：设设V，E是连通图是连通图欧拉通路欧拉通路（Euler Path）半欧拉图半欧拉图欧拉回路欧拉回路（Euler Circuit）欧拉图欧拉图 (Eulerian)说明说明规定平凡图是欧拉图；规定平凡图是欧拉图；欧拉通路是简单通路欧拉通路是简单通路,欧拉回路是简单回路；欧拉回路是简单回路；环不影响图的欧拉性。环不影响图的欧拉性。计
