Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once.
Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once.
For the existence of Eulerian trails it is necessary that zero or two vertices have an odd degree.
Determining whether Hamiltonian paths and cycles exist in graphs are NP-complete.
Euler & Hamilton App:
From the list of preloaded graphs, or those created with the edit function, the app calculates if they have an Eulerian or/and Hamiltonian path.
In each case, it only allows to start at the nodes where it is possible to make each of the paths, and marks them in green:
(Eulerian Graph with a bridge Starting nodes In green)
If there is a Hamilton path, the app calculates the shortest path. Let the user search for the shortest Hamilton path, and if not found, mark the excess distance in red.
If there are difficulties to find the shortest path, the edit mode can show the best solution:
Shortest path: ACEFBD
The editor mode allows you to create new graphs, which can be permanently incorporated into the list of graphs to study.
In the preloaded list:
Herschel Graph
No comments:
Post a Comment