欧拉图
1. 定义
1.1 欧拉通路 & 欧拉回路
- 通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的通路称作欧拉通路。
- 通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的回路称作欧拉回路。
【注】规定平凡图是欧拉图。
1.2 欧拉图 & 半欧拉图
- 具有欧拉回路的图称为欧拉图。
- 具有欧拉通路而无欧拉回路的图称作半欧拉图。
2. 性质
- 无向图 G 是欧拉图当且仅当 G 是连通图且没有奇度顶点。
- 无向图 G 是半欧拉图当且仅当 G 是连通的且恰有两个奇度顶点。
- 有向图 D 是欧拉图当且仅当 D是强连通的且每个顶点的入度等于出度。
- 有向图 D 是半欧拉图当且仅当 D是单连通的且恰有两个奇度顶点，其中一个顶点的入度比出度大 1 ，另一个顶点的出度比入度大 1 ，而其余顶点的入度等于出度。
- 无向图 G 是非平凡的欧拉图当且仅当 G是连通的且是若干个边不重的圈的并。
本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-08-31，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录