Least weight route through all vertices thatt raverses every arc at least once

Concept of a Least Weight Route That Traverses Every Arc At Least Once

This idea can be referred to as the Chinese Postman Problem (CPP) or Route Inspection Problem (RIP), a fundamental problem in graph theory and network routing.
The task is to find a least weight closed walk in a network (graph) such that every arc is traversed at least once, allowing repetition.
The CPP has significant applications in many fields, including road maintenance, DNA sequencing, and waste collection routing.

An Eulerian network is one where all vertices have even degrees. In such a network, we can start and end at the same point while traversing all arcs exactly once.
A network is Non-Eulerian if it has more than two vertices of odd degree, in which case we require copies of some arcs to ensure that we can visit every arc while maintaining the same start and end point.

Fleury’s Algorithm is a simple, though somewhat inefficient, method that can be used to solve an Eulerian network. It works by picking a random vertex, tracing the walk, and knocking out (ignoring) any arcs once crossed.
It’s important that you do not traverse a bridge (an arc which, if removed, increases the number of components) unless necessary

To transform a non-Eulerian network into an Eulerian one, we must duplicate (repeat) some arcs.
To find the least weight route, we choose to duplicate the arcs that have the least weight, creating auxiliary (additional) arcs to form a new Eulerian network.
We can then find the least weight route that traverses every arc at least once in the revised Eulerian network.

Beware of bridges in Eulerian networks - Fleury’s algorithm cannot proceed over a bridge unless there is no other option.
Repetition of arcs in non-Eulerian networks must be done intentionally. An optimal solution involves selecting arcs that minimise the total weight.
Note that a non-Eulerian network will always have at least two vertices of odd degree and hence needs duplication of arcs.

Understand the implications of Eulerian and non-Eulerian networks in real-life scenarios, such as waste collection routes or road maintenance plans.
Practice solving Chinese Postman Problems both in Eulerian circuits (using Fleury’s algorithm) and non-Eulerian circuits (by first making them Eulerian).
Coding exercises, such as an implementation of Fleury’s algorithm, can reinforce your understanding of these concepts.
Diagramming exercises are useful in visually grasping how the algorithm works, helping make sense of this complex task.