In graph theory, an Eulerian trail is a trail in a graph which visits every edge exactly once. Similarly, an Eulerian circuit is an Eulerian trail which starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. Mathematically the problem can be stated like this:
Given the graph on the top, is it possible to construct a path (or a cycle, i.e. a path starting and ending on the same vertex) which visits each edge exactly once?
The term Eulerian graph has two common meanings in graph theory. One meaning is a graph with an Eulerian circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs.
Hamiltonian Circuit is a circuit that visits each vertex once without touching any vertex more than once. (Postman problem)
Every complete graph (n>2) has a Hamilton circuit.
www.pballew.net - Special Graph Problems
No comments:
Post a Comment