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