跳到内容

在图中查找欧拉路径或回路

来源：R/eulerian.R
has_eulerian_path.Rd

has_eulerian_path() 和 has_eulerian_cycle() 检查输入图中是否存在欧拉路径或回路。eulerian_path() 和 eulerian_cycle() 返回这样的路径或回路（如果存在），否则会抛出错误。

用法

has_eulerian_path(graph)

has_eulerian_cycle(graph)

eulerian_path(graph)

eulerian_cycle(graph)

参数

图

igraph 图对象

值

对于 has_eulerian_path() 和 has_eulerian_cycle()，一个逻辑值，指示图是否包含欧拉路径或回路。对于 eulerian_path() 和 eulerian_cycle()，一个具有两个条目的命名列表

epath

一个向量，包含沿欧拉路径或回路的边 ID。

vpath

一个向量，包含沿欧拉路径或回路的顶点 ID。

详细信息

has_eulerian_path() 确定输入图是否具有欧拉路径，即恰好穿过图的每条边一次的路径，并返回一个逻辑值作为结果。eulerian_path() 返回一个可能的欧拉路径，用其边和顶点序列描述，如果不存在这样的路径则抛出错误。

has_eulerian_cycle() 确定输入图是否具有欧拉回路，即恰好穿过图的每条边一次并返回其起点的路径，并返回一个逻辑值作为结果。eulerian_cycle() 返回一个可能的欧拉回路，用其边和顶点序列描述，如果不存在这样的回路则抛出错误。

参见

图回路 feedback_arc_set(), feedback_vertex_set(), find_cycle(), girth(), is_acyclic(), is_dag(), simple_cycles()

is_eulerian(), eulerian_path(), eulerian_cycle().

示例


g <- make_graph(~ A - B - C - D - E - A - F - D - B - F - E)

has_eulerian_path(g)
#> [1] TRUE
eulerian_path(g)
#> $epath
#> + 10/10 edges from 26248dc (vertex names):
#>  [1] A--B B--C C--D B--D B--F A--F A--E D--E D--F E--F
#> 
#> $vpath
#> + 11/6 vertices, named, from 26248dc:
#>  [1] A B C D B F A E D F E
#> 

has_eulerian_cycle(g)
#> [1] FALSE
try(eulerian_cycle(g))
#> Error in eulerian_cycle(g) : 
#>   At vendor/cigraph/src/paths/eulerian.c:615 : The graph does not have an Eulerian cycle. Input problem has no solution