|
||||||||||||||||
|
||||||||||||||||
|
|
|
|
EULER'S TOUR |
|
|
An Euler's tour or path is a path through a graph which starts and ends at the same vertex and includes every edge exactly once. The well-known Königsberg bridges problem is an example of an Euler tour. Euler showed that a connected graph has an Euler path if and only if it has at most two graph vertices of odd degree. Vertices of odd degree are vertices which are connected to odd number of neighboring vertices. Thus, in order for an Euler tour to be possible, a maximum of two vertices are allowed to be connected to odd number of neighboring vertices.
|
|
|
|
