 GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/IsEulerian

GraphTheory

 IsEulerian
 test if graph is Eulerian
 FindEulerianPath
 find Eulerian path

 Calling Sequence IsEulerian(G) IsEulerian(G, T) FindEulerianPath(G)

Parameters

 G - graph T - (optional) name

Description

 • The IsEulerian command returns true if the input graph is an Eulerian graph, i.e there exists a closed walk in the graph that uses each edge exactly once. It returns false otherwise.
 • An optional second argument T is assigned an Eulerian Trail of the graph if such a trail exists, and FAIL otherwise.
 • The FindEulerianPath  commandreturns a list corresponding to an Eulerian trail if one exists, and NULL otherwise.
 • The algorithm used to construct the Eulerian trail is depth-first-search. The complexity is $\mathrm{O}\left(n+m\right)$ where n=|V| and m=|E|.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{IsEulerian}\left(\mathrm{CompleteGraph}\left(4\right)\right)$
 ${\mathrm{false}}$ (1)
 > $\mathrm{IsEulerian}\left(\mathrm{CompleteGraph}\left(5\right),'T'\right)$
 ${\mathrm{true}}$ (2)
 > $T$
 ${\mathrm{Trail}}{}\left({1}{,}{2}{,}{3}{,}{1}{,}{4}{,}{2}{,}{5}{,}{3}{,}{4}{,}{5}{,}{1}\right)$ (3)
 > $\mathrm{FindEulerianPath}\left(\mathrm{SpecialGraphs}:-\mathrm{BookGraph}\left(3\right)\right)$
 $\left[{1}{,}{2}{,}{4}{,}{3}{,}{1}{,}{5}{,}{6}{,}{2}{,}{8}{,}{7}{,}{1}\right]$ (4)

Compatibility

 • The GraphTheory[FindEulerianPath] command was introduced in Maple 2020.