首页 > 其他 > 详细

欧拉图Eulerian Graph

时间:2019-10-19 20:57:33      阅读:69      评论:0      收藏:0      [点我收藏+]

一、节点的度

无向图:节点的度为该节点所连接的边数

有向图:节点的度分为入度和出度。

二、欧拉图定义

具有欧拉回路的图称作欧拉图,具有欧拉路径而无欧拉回路的图称为半欧拉图。

欧拉回路:

? 通过图中每条边且只通过一次,并且经过每一顶点的通路。

欧拉路径:

? 通过图中每条边且只通过一次,并且经过每一顶点的回路。

判断方式:

欧拉回路 欧拉路径(欧拉通路)
无向图 每个节点的度为偶数 只有两个点的度为奇数,分别欧拉路径的起点和终点
有向图 每个节点的入度与出度相等 唯有一个点只有入度=1,一个点只有出度=1,其其他点的入度与出度相等

三、解决算法

朴素法(并查集)

HDU1878欧拉回路>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>AC代码

HDU3018Ant Trip>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>AC代码

Fleury(弗罗莱)算法

待填天坑

欧拉图Eulerian Graph

原文:https://www.cnblogs.com/trirabbits/p/11705038.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!