Administracion

NOMBRE:ENCINAS MENACHO ALEJANDRA FABIOLACI:7303317 |

¿QUE PROBLEMA INTENTO RESOLVER KENIGSBERG UTILIZANDO GRAFOS Y SI LO LOGRO?
Los puentes de Königsberg
Königsberg (actualmente Kaliningrado, Rusia) era una ciudad de Prusia del siglo XVIII. El problema que nos ocupa tiene como protagonista a un río, el río Pregel, que cruzaba la ciudad, a dos islas que se encontraban en el mismo y a sietepuentes que comunicaban las dos partes de la ciudad con las mismas. Concretamente la situación era como se describe en la imagen ( y son las dos partes de la ciudad y y las dos islas):

(Imagen tomada de Historias de la Ciencia)
El problema consistía en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto de partida. Antes de seguir leyendo podéis intentarlo vosotrosmismos, aunque os recomiendo que no le dediquéis demasiado tiempo.
Iniciación a la teoría de grafos
Un grafo es básicamente un conjunto no vacío (al menos contiene un elemento) de puntos llamados vértices y un conjunto de líneas llamadas aristas cada una de las cuales une dos vértices. Se llama lazo a una arista que une un vértice consigo mismo. Se dice que dos vértices son adyacentes si existeuna arista que los une.
Se dice que un grafo es simple si para cualesquiera dos vértices existe a lo sumo una arista que los une. En otro caso se denomina multigrafo.
Si es un vértice de un grafo, se denomina grado de al número de aristas que inciden en el mismo (por convenio de considera que un lazo cuenta dos veces al determinar el grado de su vértice).
Se dice que un grafo es conexo si no puedeexpresarse como la unión de dos grafos de vértices disjuntos. Os dejo un ejemplo:

Un camino de longitud n es una sucesión de vértices, , y aristas, , de la siguiente forma: . Se dice que un camino es cerrado si , es decir, el vértice inicial y el final son el mismo. Se dice que es simple si todas sus aristas son distintas. Se llama trayectoria a un camino simple en el que todos sus vértices(salvo probablemente el inicial y el final) son distintos y se denomina circuito a una trayectoria cerrada con al menos una arista.
Se llama camino euleriano a un camino simple que contiene todas las aristas del grafo y se denomina circuito euleriano a un camino euleriano cerrado. Se dice que un grafo es euleriano si contiene un circuito euleriano.
Resolución del problema
Para empezar, ¿quién resolvióel problema? Pues como ya sabéis los que conocíais el problema y como habréis intuido los que no lo conocíais fue Leonhard Euler quien dio solución a este asunto. La idea genial de Euler fue representar la ciudad de Königsberg como un grafo en el que las cuatro partes de la misma eran los vértices y los siete puentes eran las aristas:

Por tanto el problema de los puentes de Königsberg pasa a serun problema de teoría de grafos cuya solución publicó Euler en su artículo Solución de un problema relativo a la geometría de posición.
Según las definiciones que hemos visto en el punto anterior lo que queremos saber es si este grafo en euleriano, es decir, si contiene un circuito euleriano (es decir, un camino que contiene a todas las aristas del grafo sin que ninguna se repita y que comienza ytermina en el mismo vértice). Vamos a demostrar el siguiente resultado:
Teorema:
Un grafo es euleriano y sin vértices aislados es conexo y el grado de todos sus vértices es par.
Demostración:
* Si es euleriano entonces contiene un circuito euleriano y como no tiene vértices aislados entonces cualquier par de vértice y están conectados por la parte del circuito que va de a . Por tanto es conexo.Por otra parte, como es euleriano contiene un circuito euleriano, es decir, un camino simple y cerrado que contiene a todas las aristas. Por tanto por cada arista que llegue a un vértice debe haber otra que salga del mismo y en consecuencia el grado de cada vértice es un número par.
* Partimos de que es conexo y todos sus vértices tienen grado par.
Si el número de aristas de es 1 ó 2 el...