Networks

New Zealand

Level 7 - NCEA Level 2

Lesson

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:

- If a network has
**exactly two vertices of odd degree**, then the network has an**Euler trail**(and so it is**traversable**). These two vertices will be the start and the end of the trail. - If a network has
**no vertices of odd degree**, then the network has an**Euler circuit**(and so it is an**Euler network**).

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.

Fleury’s algorithm

- Make sure the graph has either $0$0 or $2$2 vertices with odd degree.
- If there are no edges with odd degree, start anywhere. If there are $2$2, pick one of them to start from.
- Follow edges one at a time, eliminating the edges you pick from the network as you go.
- If you have a choice between a bridge and a non-bridge from the remaining edges,
**always**choose the non-bridge.

- If you have a choice between a bridge and a non-bridge from the remaining edges,
- Stop when you run out of edges.

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:

In summary,

- A network is
**traceable**if there is a**path**that visits every vertex, and**Hamiltonian**if you can do it with a circuit (**closed**path). - A network is
**traversable**if there is a**trail**that uses every edge, and**Euler**if you can do it with a cycle (**closed**trail).

Choose appropriate networks to find optimal solutions

Apply network methods in solving problems