Waste less time on Facebook — follow Brilliant.
×

All Roads Lead To and From Rome

Everyone has heard of the famous Königsberg bridge problem, where one must traverse all seven bridges and end up back where one started without traversing a bridge twice. This is indeed impossible, as dictated by Graph Theory.

However, loosening the restriction to we must traverse each bridge exactly twice, we see that it indeed becomes possible:

imgur

imgur

Image credit Jake Lai

So, is it possible, with these new rules, to successfully traverse through any set of paths (i.e graph)?

Note by Daniel Liu
1 year, 11 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Yes, it's always possible as long as the graph is connected; moreover, it's always possible to find such tour where each edge is traversed once in each direction. The proof is also simple: just double all the edges (and orient them, for the strengthening), and see that the produced graph is Eulerian by inspecting its degrees; any such Eulerian tour has the property that it uses each original edge twice (since each original edge is doubled into two edges, where each of it is used). To find one such path, use some algorithm. Ivan Koswara · 1 year, 11 months ago

Log in to reply

@Ivan Koswara Nice! Trémaux's Maze solving algorithm is also related to this. Daniel Liu · 1 year, 11 months ago

Log in to reply

@Daniel Liu Indeed, my first idea was to use depth-first search (which is essentially a variation of Tremaux's maze solving algorithm, or the other way around), but marking edges instead of vertices; this doesn't guarantee that the result is Eulerian, however (some edges might be missed). Thus we can extend the resulting tour to cover all edges, and that's Hierholzer's algorithm. Ivan Koswara · 1 year, 11 months ago

Log in to reply

Credit me~ Jake Lai · 1 year, 11 months ago

Log in to reply

@Jake Lai OOPS I'm so sorry :(

Done Daniel Liu · 1 year, 11 months ago

Log in to reply

@Daniel Liu I was just kidding :p Jake Lai · 1 year, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...