13.1 欧拉图

无向图中的欧拉图

• 欧拉圈、欧拉图：称穿过无向图中每条边的简单闭合链为欧拉圈。有欧拉圈的图称为欧拉图。
• 若无向图 中每个顶点的次数大于1，则在 中存在圈。
• 定理13.1：连通无向图 是欧拉图当且仅当 的每个顶点都是偶顶点。
• 欧拉链：称穿过无向图 中每条边的简单非闭合链为欧拉链。(注意：欧拉链一般不是基本链)
• 定理13.2：在连通无向图 中存在连接顶点 和 的欧拉链当且仅当只有 和 是奇顶点。
  

一笔画问题

从无向图的一个顶点出发，笔不离纸，不重复地画出该图的所有边。

• 若连通无向图只有偶顶点，则从任意顶点出发，可沿欧拉圈不重复地一笔画出所有边，并回到出发点。
• 若连通无向图只有两个奇顶点，则从一个奇顶点出发，可沿欧拉链不重复地一笔画出所有边，并到达另一个奇顶点。
• 若连通无向图有多于两个奇顶点，则不能不重复地画出该图的所有边。

有向图中的欧拉图

• 欧拉回路、欧拉图：称穿过有向图中每条弧的简单回路为欧拉回路。有欧拉回路的有向图称为欧拉图。
• 欧拉通路：称穿过有向图中每条弧且非闭合的简单通路为欧拉通路。
• 强连通有向图 是欧拉图当且仅当 中每个顶点的引入次数与引出次数相同。
• 单向连通有向图 有从顶点 到 的欧拉通路当且仅当 的引出次数比引入次数大1， 的引入次数比引出次数大1， 中其它顶点的引入次数与引出次数相同。
  
  
  

13.2 哈密顿图

• 哈密顿圈、哈密顿回路、哈密顿图

  • 称穿过无向图 中每个顶点一次且仅一次的圈为哈密顿圈。
  • 称穿过有向图 中每个顶点的基本回路为哈密顿回路。
  • 有哈密顿圈或哈密顿回路的图称为哈密顿图。

• 哈密顿链：称穿过无向图 中每个顶点的基本链（顶点不同的链）为哈密顿链。

• 哈密顿通路：称穿过有向图 中每个顶点的基本通路为哈密顿通路。

• 从哈密顿回路中去掉一条弧就成为哈密顿通路，从哈密顿圈中去掉一条边就成为哈密顿链。哈密顿回路是完备回路，哈密顿通路是完备通路，所以有向哈密顿图是强连通的，存在哈密顿通路的有向图是单向连通的。存在哈密顿链的无向图是连通的。

• 哈密顿图的必要条件（只能判断不是哈密顿图）：若无向图 ＝ 是哈密顿图， 是 的非空真子集，则 。其中 是从 中删除 中所有顶点及它们关联的边所得子图的连通分支数。
  

• 哈密顿链的必要条件（只能判断不是哈密顿链）：若无向图 ＝ 有哈密顿链， 是 的非空真子集，则 。其中 是从 中删除 中所有顶点及它们关联的边所得子图的连通分支数。
  

• 定理13.3（哈密顿链的充分条件）：若 阶简单无向图 中每对不相邻顶点次数之和 ，则在 中存在哈密顿链。

• 哈密顿图的充分条件：设 ，若 阶简单无向图 中每对不相邻顶点次数之和 ，则 是哈密顿图。

• 定理13.4：在有向完全图中必存在哈密顿通路。

• 凡是强连通的有向完全图一定有哈密顿回路。