The famous Königsberg bridge problem, considered by many as the origin of graph theory, asks if all city bridges can be crossed without repetition in a single trip.
Euler proved that it was impossible to do that. One of the reasons for that was:
- The nodes have different degrees.
- One or more nodes with an odd degree make a single trip impossible.
- The four nodes (pieces of land) had an odd degre (number of bridges).
- A single trip is only possible when the number of lands are equal to the number of bridges.
- None of the above.
Original idea by: Lucas Carvalho Roncoroni.
No comments:
Post a Comment