几类重要图

欧拉图

问题的提出

欧拉图的概念

• 给定无孤立结点的无向图\(G\)，经过图G每边一次且仅一次的迹称为欧拉路
• 给定无孤立节点的无向图\(G\)，经过图G每边一次且仅一次的闭迹称为欧拉回路
• 连通图\(G\)具有欧拉回路当且仅当它的每一个顶点都有偶数度
• 连通图\(G\)具有欧拉路而无欧拉回路，当且仅当\(G\)恰有两个奇数度结点

  有向图中则称为有向欧拉（路、回路）

Fleury算法

中国邮路问题

哈密尔顿图

概念

• 设无向图G，经过图G的每个结点一次且仅一次的路称为哈密顿路
• 经过图G的每个结点一次且仅一次的闭路称为哈密顿回路
• 有向路同理

  如何区分欧拉图与哈密顿图 - 欧拉图是针对边进行讨论 - 经过每个边一次且仅一次 - 哈密顿图针对结点进行讨论 - 经过每个结点一次且仅一次