离散数学——欧拉图复习
定义:一条通过一个图的每条边一次且仅一次,并且经过图中每个顶点的路径称为欧拉路径或欧拉迹。欧拉路径的现有图形称为欧拉图。
定理1:无向图G有欧拉路径当且仅当G是有零个或两个奇数顶点的连通图。如果没有奇点顶点,则路径是环;如果有两个奇数顶点,它们就是每条欧拉路径的端点。
推断出无向图G是欧拉图(有欧拉路径)当且仅当G是连通图,且G中没有四分之一顶点。
定理2:有向图D有欧拉路,当且仅当D是连通的,且除两个顶点外所有顶点的入口度等于出口度。两个特殊顶点中,一个顶点的入度比出度大1,另一个顶点的入度比出度小1。
位律师回复
0条评论