Trains @ Königsberg

Computer Science Level 5

The above image represents a map of Königsberg. The green areas are land and the yellow lines are bridges.

The emperor of the kingdom wants to set up a train service that transports people from a landmass to another within the empire using the bridges.

There are people in the red castle who want to go to the blue castle subject to the following conditions:

  • The route cannot traverse a bridge twice.
  • The route can visit a landmass numerous times, including the land of the red castle.
  • The route stops the first time it reaches the blue castle.

How many possible train routes could they take?


Problem Loading...

Note Loading...

Set Loading...