Puentes de koenigsberg

Universidad Fermín Toro
Facultad de Ingeniera
Cabudare – Edo Lara

‘7 Puentes de Konigsberg’



La ciudad de Kaliningrado, antiguamente llamada Königsberg, es un lugar situado en la desembocadura del río Pregolya, en la antigua Prusia Oriental. Este río atravesaba la ciudad, dividiendo la zona en varias partes. Para no perder la comunicación, ésta estaba llena de un sistema de puentesconectores. En total, había siete grandes puentes en Kaliningrado: El puente del herrero, el puente conector, el puente verde, el puente del mercado, el puente de madera, el puente alto y, por último, el puente de la miel. El problema consistía en comenzar en un punto, pasar por los siete puentes sin repetir ninguno y volver al punto de partida. Fue Euler quien fue represento la ciudad de Königsbergcomo 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 ser un 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”.

Bases Teóricas
Grafos:
Definiciones Básicas
Un grafo es básicamente unconjunto de puntos se dice que es 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 existe una arista que los une, es decir comparten la misma arista.
Si  es un vértice de un grafo, sedenomina 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 puede expresarse como la unión de dos grafos de vértices disjuntos.
Se llama trayectoria a un camino simple en el que todos sus vértices (salvo probablemente el inicial y el final) son distintos y sedenomina 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.

Clasificación:

* Grafo simple G(V,E) consta de V , un conjunto no vacío de vértices, y de E, un conjunto de pares noordenados de elementos distintos de V . A esos pares se les llama aristas o lados. En algunos casos lo grafos simples no bastan para modelar ciertas situaciones en las cuales se requiere de la existencia de múltiples aristas entre par de vértices. En este caso no es suficiente definir las aristas como par de vértices.

* Multigrafo G(V,E) consta de un conjunto V de vértices, un conjunto E dearistas y una función f de E en {{u, v}|u, v ∈ V, u 6= v}. Se dice que las aristas e1, e2 son aristas múltiples o paralelas si f(e1) = f(e2). Los multigrafos definidos no admiten bucles o lazos (aristas que conectan un vértice consigo mismo). Usamos en este caso, pseudografos que son más generales que los multigrafos.

* Pseudografo G(V,E) consta de un conjunto V de vértices, un conjunto E dearistas y una función f de E en {{u, v}|u, v ∈ V }. Se dice que una arista e es un bucle o lazo si f(e) = {u, u} = {u} para algún u ∈ V .

* Grafo dirigido o dígrafo G = (V,E) consta de un conjunto V de vértices, un conjunto E de aristas, que son pares ordenados de elementos de V .

* Multigrafo dirigido G(V,E) consta de un conjunto V de vértices, un conjunto E de aristas y una funciónf de E en {(u, v)|u, v ∈ V } Se dice que las aristas e1, e2 son aristas múltiples o paralelas si f(e1) = f(e2).
La diferencia entre grafo y digrafo es que el último tiene los lados dirigidos y se entiende como un grafo dirigido.

Teniendo ya nociones básicas referentes a grafos es posible representar concretamente la situación referente al problema de los 7 puentes de konigsbergs el grafo...