find_euler {gor}

Constructing an Eulerian Cycle

Description

It finds an Eulerian cycle using a O(q) algorithm where q is the number of edges of the graph.

Usage

find_euler(G, v)

Arguments

G

Eulerian and connected graph

v

Any vertex as starting point of the cycle

Details

Recursive algorithm for undirected graphs. The input graph should be Eulerian and connected.

Value

A two-element list: the $walk component is a q\times2 matrix edgelist, and the $graph component is the input graph with no edges; it is used in intermediate steps, when the function calls itself.

Disclaimer

This function is part of the subject "Graphs and Network Optimization". It is designed for teaching purposes only, and not for production.

• It is introduced in the "Connectivity" section.

• It is used as a subroutine in the "TSP" section.

Author(s)

Cesar Asensio (2021)

References

Korte, Vygen: Combinatorial Optimization (Springer) sec 2.4.

See Also

build_tour_2tree double-tree algorithm.

Examples

library(igraph)
find_euler(make_full_graph(5), 1)$walk   # Walk of length 10