Grafos

Los grafos y la actividad humana
Los orígenes de la teoría de grafos se encuentran en el siglo XVIII aproximadamente, por una de las mentes más sobresalientes e importante en la historia; merefiero al matemático Leonhard Euler, quien en 1736 participa en la resolución del conocido “problema de los puentes de Köningsberg”.
Este era un puerto que se localizaba en la antigua Alemania; lacual actualmente se encuentra en Rusia y se llama Kaliningrado, cerca del rio Pregel. “El rio dividía la ciudad en cuatro áreas de tierras separadas, y había siete puentes que les permitía a loshabitantes de Köningsberg cruzar el rio para trasladarse de una parte a otra de la ciudad…” (Combariza, s.f, 567)


Figura 1
Köningsberg en la época de Euler
Fuente:https://sities.google.com/site/sevenbridgesofkonigsberg/
Los habitantes de Köningsberg se planteaban una pregunta que da origen a esta teoría de los grafos; ¿será posible recorrer la ciudad cruzando cada uno de los puentes solamenteuna vez? A raíz de esta interrogante Leonhard realiza el primer modelo grafico.
Sobre esta incógnita Combariza (s.f) explica:
Euler hizo un modelo matemático del problema. Es decir, solo tomó lainformación relevante de este y se deshizo de hechos como la longitud de los puentes o el área de cada región, y se concentró en la relación entre las ciudades y los puentes, nombrando a cadacuidad como un punto y a cada puente simplemente como una línea que une dos ciudades. (p.568)
El “modelo matemático” que utilizó Euler fue el siguiente:



Figura 2
Grafo utilizado por EulerFuente: http://albertopiedrabuena.blogspot.com/2008/04/los-puentes-de-knigsberg.html
Para comprender mejor el tema de grafos es de suma importancia definir algunos conceptos relevantes en estateoría:
Grafo: es un conjunto de vértices (V) o nodos unidos por aristas (A) o arcos.
Vértice o nodos: este término hace referencia al elemento principal que integran los grafos.
Arista o arcos: es la...