西安电子科技大学欧拉图$6.4.1 区软件学院即G中得每一条边在且仅在E,,E,，,E的一个之中。现将简单回路集E,EEm连接成一条简单回路。从E，开始，由于G是连通的，所以在EE中至少有一个，设为E，满足E，与E至少有一个公共结点设为V。（否则由E，导出的子图是一个单独的连通分支，这与G是连通的矛盾。）设E,-(v, Vin, Vi2, Vi3,"", Vim, V), E,= (v, Vj1Vij2 , Vj3,"", Vit, V)则(v,Vi,Vi2，Vi"",VimV,Vj1,Vj2，Vjs"",Vit，V)是一条简单回路，记为E(1)。将E，与E，从简单回路集中删除，将E(1)插入其中。如此下去，直到简单回路集中仅剩下一条回路，即为欧拉回路。故G是欧拉图。西安电子科技大学 §6.4.1 欧拉图 软件学院 即G中得每一条边在且仅在E1,E2,.,Em的一个 之中。 现将简单回路集{E1,E2,.,Em|}连接成一条简单 回路。从E1开始，由于G是连通的，所以在 {E2,.,Em}中至少有一个，设为Ep，满足E1与Ep至 少有一个公共结点设为v。（否则由E1导出的子图 是一个单独的连通分支，这与G是连通的矛盾。） 设E1=(v, v i1, v i2 , v i3,., v im, v)，Ep= (v, v j1, v j2 , v j3,., vjt, v) 则(v, v i1, v i2 , v i3,., v im, v, v j1, v j2 , v j3,., vjt, v)是一条简单回路 ，记为E(1) 。 将E1与Ep从简单回路集中删除，将E(1)插入其中。 . 如此下去，直到简单回路集中仅剩下一条回路，即为欧拉回路。 故G是欧拉图