503
edits
Crunching the numbers: Graph theory (view source)
Revision as of 06:58, 7 August 2011
, 7 August 2011no edit summary
(Created page with "{{Article| type=column | picture=GraphTheory1.png | caption=Can you cross each bridge only once? | weekday=Sunday | day=7 | month=8 | year=2011 | time=06:08:48 | discusstype=none...") |
mNo edit summary |
||
| Line 30: | Line 30: | ||
He then made the observation that if a landmass was not a place to either start or finish, then there should be an even number of bridges so that half of the bridges would be used to get to the landmass and the other half would be used to leave. Since all four of the nodes had an odd number of edges, that would mean each landmass is an endpoint. As there could only be two endpoints (a place to start and a place to finish), then it was impossible to cross each bridge only once. | He then made the observation that if a landmass was not a place to either start or finish, then there should be an even number of bridges so that half of the bridges would be used to get to the landmass and the other half would be used to leave. Since all four of the nodes had an odd number of edges, that would mean each landmass is an endpoint. As there could only be two endpoints (a place to start and a place to finish), then it was impossible to cross each bridge only once. | ||
Euler’s proof created an entirely new branch of mathematics called graph theory. Whether game designers have realized it or not, many puzzles can easily be represented with graph theory, making them substantially easier to solve. One such type of puzzle often stumped me as a kid: sliding ice puzzles. These brainteasers have shown up in the icy areas of Pokémon since {{bp|Generation II}}, but they aren’t unique to Game Freak’s creation. In Golden Sun, many djinn are obtained by correctly sliding down the right path, and in {{wp|Tales of | Euler’s proof created an entirely new branch of mathematics called graph theory. Whether game designers have realized it or not, many puzzles can easily be represented with graph theory, making them substantially easier to solve. One such type of puzzle often stumped me as a kid: sliding ice puzzles. These brainteasers have shown up in the icy areas of Pokémon since {{bp|Generation II}}, but they aren’t unique to Game Freak’s creation. In Golden Sun, many djinn are obtained by correctly sliding down the right path, and in {{wp|Tales of Symphonia}}, one such puzzle was done in space rather than on ice. | ||
Let’s take a look at a sliding ice puzzle found in the Generation II version of the Ice Path: | Let’s take a look at a sliding ice puzzle found in the Generation II version of the Ice Path: | ||