离散数学--Chap15 欧拉图与哈密顿图
Chap15 欧拉图与哈密顿图
核心知识点
欧拉图
欧拉回路（通路）
遍历图中所有边一次且仅一次的回路（通路）
欧拉图（半欧拉图）
含有欧拉回路（通路）的图
求欧拉回路的算法--Fleury算法
基本思想：尽量不走桥
判别方法
无向图G无奇度顶点
哈密顿图
哈密顿回路（通路）
遍历图中所有点一次且仅一次的回路（通路）
哈密顿图（半哈密顿图）
含有哈密顿回路（通路）的图
带权图
Dijkstra算法
一般知识点
最短路问题、中国邮递员问题、货郎担问题
最短路问题用Dijkstra算法解决
竞赛图
竞赛图是通过在无向完全图中为每个边缘分配方向而获得的有向图
参考书籍：离散数学（第2版）--屈婉婷、耿素云、张立昂
