Chap15 欧拉图与哈密顿图

核心知识点

欧拉图

欧拉回路（通路）

遍历图中所有边一次且仅一次的回路（通路）

欧拉图（半欧拉图）

含有欧拉回路（通路）的图

求欧拉回路的算法--Fleury算法

基本思想：尽量不走桥

判别方法

无向图G无奇度顶点

哈密顿图

哈密顿回路（通路）

遍历图中所有点一次且仅一次的回路（通路）

哈密顿图（半哈密顿图）

含有哈密顿回路（通路）的图

带权图

Dijkstra算法

一般知识点

最短路问题、中国邮递员问题、货郎担问题

最短路问题用Dijkstra算法解决

竞赛图

竞赛图是通过在无向完全图中为每个边缘分配方向而获得的有向图

参考书籍：离散数学（第2版）--屈婉婷、耿素云、张立昂