欧拉图
1. 定义
1.1 欧拉通路 & 欧拉回路
-
通过图(无向图或有向图)中所有边一次且仅一次行遍所有顶点的通路称作欧拉通路。
-
通过图(无向图或有向图)中所有边一次且仅一次行遍所有顶点的回路称作欧拉回路。
【注】规定平凡图是欧拉图。
1.2 欧拉图 & 半欧拉图
-
具有欧拉回路的图称为欧拉图。
-
具有欧拉通路而无欧拉回路的图称作半欧拉图。
2. 性质
-
无向图 是欧拉图当且仅当 是连通图且没有奇度顶点。
-
无向图 是半欧拉图当且仅当 是连通的且恰有两个奇度顶点。
-
有向图 是欧拉图当且仅当 是强连通的且每个顶点的入度等于出度。
-
有向图 是半欧拉图当且仅当 是单连通的且恰有两个奇度顶点,其中一个顶点的入度比出度大 1 ,另一个顶点的出度比入度大 1 ,而其余顶点的入度等于出度。
-
无向图 是非平凡的欧拉图当且仅当 是连通的且是若干个边不重的圈的并。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 お前はどこまで見えている!
评论
WalineTwikoo