更新时间:2024-02-26 11:03:23
大家好,我是小环,我来为大家解答以上问题。欧拉图片数学家,欧拉图很多人还不知道,现在让我们一起来看看吧!
1、定义:经过图中每条边一次且仅一次并且行遍图中每个顶点的通路(回路),称为欧拉通路或欧拉迹(欧拉回路或欧拉闭迹),存在欧拉回路的图称为欧拉图。
2、 以下是无向图和有向图是否存在欧拉通路或回路的判别法: 定理1:无向图具有欧拉通路,当且仅当G是连通图且有0个或两个奇度顶点。
3、若无奇度顶点,则通路为回路;若有两个奇度顶点,则它们是每条欧拉通路的端点。
4、 推论1:无向图G为欧拉图(具有欧拉回路)当且仅当G是连通的,且G中无奇度顶点。
5、 定理2:一个有向图D具有欧拉通路,当且仅当D是连通的,且除了两个顶点外,其余顶点的入度均等于出度。
6、这两个特殊的顶点中,一个顶点的入度比出度大1,另一个顶点的入度比出度小1. 推论2:一个有向图D是欧拉图(具有欧拉回路),当且仅当D是连通的,且所有顶点的入度等于出度。
本文到此讲解完毕了,希望对大家有帮助。