Oleksii Trekhleb | Javascript algorithms (Eulerian path)
This is a series of books diving deep into the core mechanisms of the JavaScript language.
· 1 phút đọc.
In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph which visits every edge exactly once. Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail which starts and ends on the same vertex.
Euler proved that a necessary condition for the existence of Eulerian circuits is that all vertices in the graph have an even degree, and stated that connected graphs with all vertices of even degree have an Eulerian circuit.
Every vertex of this graph has an even degree. Therefore, this is an Eulerian graph. Following the edges in alphabetical order gives an Eulerian circuit/cycle.
For the existence of Eulerian trails it is necessary that zero or two vertices have an odd degree; this means the Königsberg graph is not Eulerian. If there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called semi-Eulerian.
The Königsberg Bridges multigraph. This multigraph is not Eulerian, therefore, a solution does not exist.
