图论-欧拉与哈密顿的那些事儿

图论的题目真是有趣QwQ
本篇文章将介绍欧拉路径、欧拉回路、哈密顿路径和哈密顿圈等知识的定义、性质、判定及简单应用。

在生活中，一些图形是可以一笔画出的。同样地，在图G中，若一条路径恰好经过每条边一次，则称这条路径为图G的一条欧拉路径.

在图G中，若一条路径的起点和终点相同，且这条路径恰好经过每条边一次，则称这条路径为图G的一条欧拉回路.

• 图G是连通图
• 若图G是无向图，则G中度数为奇数的顶点只能有0个或2个
• 若图G是有向图，则G中存在两个入度与出度不相等的顶点：其中一个出度比入度大1，为路径的起点；另一个入度比出度大1，为路径的终点。