欧拉图

欧拉图

• 欧拉图
  • 欧拉通（回）路：通过图中所有边一次，且仅一次行遍所有顶点的通（回）路
  • 欧拉图：有欧拉回路
  • 半欧拉图：有欧拉通路而无欧拉回路
• 欧拉图判定：
  • 无向
    • G 的所有顶点的度数都是偶数
    • G 是若干个边不重的圈的并
  • 有向
    • D 的所有顶点的出度和入度相等;
    • D 是若干个边不重的有向初等回路的并。
• 半欧拉图判定：
  • 无向
    • 当且仅当 G 是连通的，且恰好只有两个奇度顶点（始，终）。
  • 有向
    • 当且仅当 D 是单向连通的且恰好有两个奇度顶点，其中一个奇度顶点的入度比出度大 1（终点），另一个 奇度顶点的出度比入度大 1（起点），而其余顶点的入度等于出度。