Amazingly, it is possible to determine if an undirected network will have an Euler trail or circuit without having to actually find it! Here’s how to tell:
Still, it can take some practice to get proficient at being able to find Euler trails or Euler circuits - knowing they exist is not the same as seeing one in front of you! To help us we are going to us a procedure called Fleury's Algorithm (pronounced FLOO-ree). It was first published by a French mathematician named M. Fleury in 1883 - the 'M.' likely stands for 'Monsieur', so their first name was lost to history.
Seems simple enough - let’s try it out:
This algorithm will find the Euler trail (or circuit) every time. It helps best in the tricky situations where you don’t know which edge to pick - if you choose a bridge before a non-bridge you won’t be able to get back.
For directed networks, we can still have Euler trails and Euler circuits, but there’s no easy way to find them like there is for undirected networks, you just have to give it a go. Let’s return once again to the garbage collection example from earlier:
Can you find the Euler circuit now you know Fleury's algorithm? Since you’re looking for a circuit, it doesn’t matter which vertex you start from. Use the Hamiltonian cycle we found earlier to help you.
One final note before we finish this section: a network can be a traversable/Euler network, a traceable/Hamiltonian network, both, or neither, as these examples demonstrate:
Choose appropriate networks to find optimal solutions
Apply network methods in solving problems