Entradas
Is this possible?
Solution:
Euler's solution to the problem of the Königsberg bridges involved the observation that when a vertex is "visited" in the middle of the process of tracing a graph, there must be an edge coming into the vertex, and another edge leaving it; and so the order of the vertex must be an even number. This must be true for all but at most two of the vertices--the one you start at, and the one you end at, and so a connected graph is traversible if and only if it has at most two vertices of odd order. Now a quick look at the graph above shows that there are more than two vertices of odd order, and so the graph cannot be traced; that is the desired walking tour of Königsberg is impossible.
1 comentarios:
Very interesting. I always thought it could be possible to visit all of the banks in one track. Thank you very much!
Publicar un comentario