离散数学——欧拉图复习

定义:一条通过一个图的每条边一次且仅一次，并且经过图中每个顶点的路径称为欧拉路径或欧拉迹。欧拉路径的现有图形称为欧拉图。

定理1:无向图G有欧拉路径当且仅当G是有零个或两个奇数顶点的连通图。如果没有奇点顶点，则路径是环；如果有两个奇数顶点，它们就是每条欧拉路径的端点。

推断出无向图G是欧拉图(有欧拉路径)当且仅当G是连通图，且G中没有四分之一顶点。

定理2:有向图D有欧拉路，当且仅当D是连通的，且除两个顶点外所有顶点的入口度等于出口度。两个特殊顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。