Wednesday, May 18, 2011

Seven Bridges of Königsberg (Unsolvable Puzzle in Computer Science))

The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler in 1735 laid the foundations of graph theory and prefigured the idea of topology.

The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges.

The problem was to find a walk through the city that would cross each bridge once and only once. The islands could not be reached by any route other than the bridges, and every bridge must have been crossed completely every time (one could not walk half way onto the bridge and then turn around and later cross the other half from the other side).

Map of Königsberg in Euler's time showing the actual layout of the seven bridges, highlighting the river Pregel and the bridges

Data Structure Can be Used to Represent The Puzzle: Graph

Solution. (Unsolvable Puzzle in Computer Science)

Reason: Its application of Graph Data Structure (Idea Comes In Mind as Studied The Puzzle Carefully). so we have to traverse each bridge one & only once & returned back to source vertex if we draw the graph of this problem we found that each vertex has odd degree so its not possible to satisfy the puzzle solution. in 17's Euler already proved it unsolvable problem of computer science & said we can solve this if we have each vertex of even degree.

See This Graph Representation

Fell Free to Comment & Suggest your Approach

No comments: