GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

Parameters

Description

Examples

Compatibility

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 On+m where n=|V| and m=|E|.

Examples

withGraphTheory:

IsEulerianCompleteGraph4

false

(1)

IsEulerianCompleteGraph5,T

true

(2)

T

Trail1,2,3,1,4,2,5,3,4,5,1

(3)

FindEulerianPathSpecialGraphs:-BookGraph3

1,2,4,3,1,5,6,2,8,7,1

(4)

Compatibility

• 

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

• 

For more information on Maple 2020 changes, see Updates in Maple 2020.

See Also

IsHamiltonian

Trail