Königsberg (hoy Kaliningrado en Rusia) era en tiempos de Euler (siglo XVIII) una ciudad cruzada por siete puentes. Durante la época se suscitó la cuestión no resuelta de si era posible recorrer toda la ciudad cruzando cada uno de los puentes una y sólo una vez. Si hacemos una representación esquemática de la ciudad vemos que los puentes unen cuatro porciones de tierra. La búsqueda por prueba y error no conduce a ningún resultado.
El problema de los puentes de Königsberg. Esta ciudad esta recorrida por el río Pregel que crea dos islas. ¿Se puede recorrer toda la ciudad pasando una sola vez por todos y cada uno de los 7 puentes que unen la parte insular de la ciudad con el resto?
La solución de Leonhard Euler. El famoso matemático abstrajo los detalles de la forma de la ciudad y sus puentes para quedarse con la conectividad, dando lugar a una de los primeros grafos. El orden de todos los vértices es impar, lo que implica que es imposible recorrerlos pasando una sola vez por cada uno.
Euler realizó una abstracción del problema representando mediante puntos las cuatro porciones de terreno y dibujando un arco entre cada dos puntos por cada puente. Llamó orden de cada vértice al numero de arcos que se reunían en el y se percató que el orden de cada vértice visitado en un recorrido sin saltos ha de ser par (sale un enlace y entra otro) excepto para dos puntos del grafo: aquellos donde se inicia y donde se acaba el recorrido, que han de tener orden impar. Si el vértice donde se inicia y se acaba son el mismo entonces todos los vértices han de ser de orden par.
En el problema de Königsberg el orden de todos los nodos es 3, esto es impar, por lo que quedó claro que no existía solución para el problema. No había un camino que recorriese todos los puentes pasando una sola vez por cada uno de ellos.
Grafos isomorfos y Bipartitos
Vértice fuente
Son los vértices de los que salen aristas sin que llegue ninguna.
Vértice sifón
Son los vértices de los que llegan aristas y no salen.
2 comentarios:
hay dios profe yo no veo pregunta por ningun lado ,que hallan dejado el grupo tres para responder
un grafo bipartito es el que no esta dirigido cuyos vértices se pueden separar en dos conjuntos disjuntos V1 y V2 y un grafo isomorfo es uno igual al primero que tenga la misma direccion y las vertices fuente es un vértice con grado de entrada cero,
Publicar un comentario