Lesson 6

It is easy to see that this grid graph is not Eulerian: it has many vertices of odd degree. Thus, it is impossible to traverse each street exactly once. Therefore, our task reduces to minimizing the number of times we traverse streets we have already visited. In graph terms, we want to add the fewest parallel edges to make it Eulerian.

This problem of “eulerization” of a graph can be solved as follows. We create a new graph whose vertices are the odd-degree vertices of the original graph. We add an edge between two vertices with a weight equal to the shortest path length between them in the original graph. We find a minimum weight perfect matching in this graph and add the corresponding paths to the original graph.

import networkx as nx

grid = nx.MultiGraph(nx.grid_2d_graph(m=6, n=6))
grid = nx.eulerize(grid)
print(nx.number_of_edges(grid))
cycle = nx.eulerian_circuit(grid, source=(0, 0))
print('→'.join(str(edge[0]) for edge in cycle))

68
(0, 0)→(0, 1)→(0, 2)→(0, 3)→(0, 4)→(0, 5)→(1, 5)→(2, 5)→(3, 5)→
(4, 5)→(5, 5)→(5, 4)→(5, 3)→(5, 4)→(4, 4)→(4, 5)→(3, 5)→(3, 4)→
(4, 4)→(4, 3)→(5, 3)→(5, 2)→(5, 1)→(5, 2)→(4, 2)→(4, 3)→(3, 3)→
(3, 4)→(2, 4)→(2, 5)→(1, 5)→(1, 4)→(2, 4)→(2, 3)→(3, 3)→(3, 2)→
(4, 2)→(4, 1)→(5, 1)→(5, 0)→(4, 0)→(4, 1)→(3, 1)→(3, 2)→(2, 2)→
(2, 3)→(1, 3)→(1, 4)→(0, 4)→(0, 3)→(1, 3)→(1, 2)→(2, 2)→(2, 1)→
(3, 1)→(3, 0)→(4, 0)→(3, 0)→(2, 0)→(2, 1)→(1, 1)→(1, 2)→(0, 2)→
(0, 1)→(1, 1)→(1, 0)→(2, 0)→(1, 0)