欧拉回路

2015/2/2 posted in  算法&数据结构

概念

对于无向图

  1. 设G是连通无向图,则称经过G的每一条边并且仅一次的路径为欧拉通路
  2. 如果欧拉通路是回路(起点和终点是同一个顶点),则称此回路为欧拉回路
  3. 具有欧拉回路的无向图G称为欧拉图

对于有向图

  1. 设D是有向图,D的基图(有向图对应的无方向的无向图)相连通,则称经过D的每一条边并且仅一次的有向路径为有向欧拉通路
  2. 具有有向欧拉通路是有向回路,则称此有向回路为有向欧拉回路。
  3. 具有有向欧拉回路的有向图D称为有向欧拉图。

定理

定理1:无向图G存在欧拉通路的充要条件是:G为连通图,并且G仅有两个奇度节点(度数为奇数的顶点)或者无奇度结点。

推论1

  1. 当G是仅有两个奇度结点的连通图时,G的欧拉通路必以此两个顶点为端点、
  2. 当G是无奇度结点的连通图时,G必为欧拉回路。
  3. G为欧拉图(存在欧拉回路)的充分必要条件是G为无奇度结点的连通图、

定理2:有向图D存在欧拉通路的充要条件是:D为有向图,D的基图连通,并且所有顶点的出度和入度都相等;或则除两个顶点外,其余顶点的出度与入度都相等,而这两个顶点中的一个顶点的出度和入度只差为1,另一个顶点的出度与入度之差为-1。

推论2

  1. 当D除出入度只差为1,-1的两个顶点之外,其余顶点的出度入度都相等时,D的有向欧拉通路必以出入度之差为1的顶点作为始点,以出入度之差为-1的顶点作为终点。
  2. 当D的所有顶点的出入度都相等时,D中存在有向欧拉回路。
  3. 有向图D为有向欧拉图的充分必要条件是D的基图为连通图,并且所有顶点的出入度都相等。

 判断

判断欧拉通路

无向图:

  1. 判断是否连通
  2. 统计出度入度
  3. 统计奇度点(有则仅有2个或一个没有)

有向图:

  1. 判断基图连通
  2. 统计所有顶点的出度入度
  3. 所有顶点的出度入度相等或出两个顶点外其余顶点的出度或入度都相等,而这两个顶点中一个出度与入度只差为1,另一个人为-1

判断欧拉回路

无向图

  1. 先判断是不是欧拉通路
  2. 保证没有奇度点

有向图

  1. 先判断是否是欧拉通路
  2. 保证所有顶点的出、入度相等