In the summer of 1735 Leonhard Euler (pronounced .Oiler.), the famous Swiss mathematician,was walking the bridges of the East Prussian town of K¨onigsberg. After a while, henoticed in frustration that, no matter where he started his walk, no matter how cleverly he continued, it was impossible to cross each bridge exactly once. And from this silly ambition,the field of graph theory was born.
Euler identified at once the roots of the park's deficiency. First, you turn the map of the
park into a graph whose vertices are the four land masses (two islands, two banks) and whose edges are the seven bridges:
This graph has multiple edges between two vertices.a feature we have not been allowing so far in this book, but one that is meaningful for this particular problem, since each bridge must be accounted for separately. We are looking for a path that goes through each edge exactly once (the path is allowed to repeat vertices). In other words, we are asking this question: When can a graph be drawn without lifting the pencil from the paper?
The answer discovered by Euler is simple, elegant, and intuitive: If and only if (a) the
graph is connected and (b) every vertex, with the possible exception of two vertices (the start and final vertices of the walk), has even degree . This is why K¨onigsberg's park was impossible to traverse: all four vertices have odd degree.
To put it in terms of our present concerns, let us define a search problem called Euler
PATH.
Euler identified at once the roots of the park's deficiency. First, you turn the map of the
park into a graph whose vertices are the four land masses (two islands, two banks) and whose edges are the seven bridges:
This graph has multiple edges between two vertices.a feature we have not been allowing so far in this book, but one that is meaningful for this particular problem, since each bridge must be accounted for separately. We are looking for a path that goes through each edge exactly once (the path is allowed to repeat vertices). In other words, we are asking this question: When can a graph be drawn without lifting the pencil from the paper?
The answer discovered by Euler is simple, elegant, and intuitive: If and only if (a) the
graph is connected and (b) every vertex, with the possible exception of two vertices (the start and final vertices of the walk), has even degree . This is why K¨onigsberg's park was impossible to traverse: all four vertices have odd degree.
To put it in terms of our present concerns, let us define a search problem called Euler
PATH.
sands casino nc-9 - SEGA Online Casino
ReplyDeleteWelcome to the sands casino happyluke and discover the excitement 샌즈카지노 of a thrilling game filled with thrilling jackpots! Click to dafabet claim your bonus and play today!