The sprinkler truck problem
Task number: 4178
Find an algorithm for finding the shortest closed walk that contains all edges of a given graph (a walk is a sequence of consecutive edges, where both edges and vertices may repeat).
For simplicity assume that the graph has at most 6 vertices of odd degree.
Solution
We construct an auxiliary complete graph on the vertices of the odd degree whose edges will be labeled by the distance of these vertices in the original graph.
The matching of the minimum weight corresponds to the sections of the walk that need to be traversed twice. If we double the edges along these paths, we get an Eulerian graph, the closed Eulerian tril of which is found by using the standard algorithm for this problem.
A matching of the minimum weight can be found by brute force (if the auxiliary graph is small as in our assignment), or by one of the sophisticated algorithms for this problem.
