【基本概念】 欧拉通路:通过图中所有边一次且仅一次行遍所有顶点的通路 欧拉回路:通过图中所有边一次且仅一次行遍所有顶点的回路 欧拉图:具有欧拉回路的图 半欧拉图:具有欧拉通路而无欧拉回路的图 奇度点:与点相连的边的数目为奇数的点 偶度点:与点相连的边的数目为偶数的点 【欧拉通路/回路的判定】 1.无向图 1)欧拉通路:图是连通的,图中只有两个奇度点,分别是欧拉通路的两个端点 对于欧拉通路,除起点、终点外,每个点如果进入,显然一定要出去,因此都是偶点 2)欧拉回路:图是连通的,点均为偶度点 对于欧拉回路,每个点进入、…

2019年1月22日 0条评论 0点热度 阅读全文