【图论】欧拉圈与哈密顿圈

欧拉迹和圈

包含所有边仅一次的迹。

一般图中欧拉迹　存在的必要条件：每个顶点度数为偶数。

一般连通图中欧拉圈　存在的充要条件：每个顶点度数为偶数。

对有向图：

如果是构成欧拉圈的话，条件是无奇点，且各点指向和背离的线数相同。

如果是构成欧拉迹的话，条件是恰有两个奇点，两个奇点分别是指向比背离的线数多一条和少一条。其余各点指向和背离的线数相同。

哈密顿链和圈

　　哈密顿链：包含所有顶点仅一次的链。

　　哈密顿圈：闭的哈密顿链。