Grafos y redes

GRAFOS

1. Introducción

El nacimiento del concepto GRAFOS se puede situar, por el año 1730, cuando Euler (matemático) se convirtió en el padre de la Teoría de Grafos al modelar un famoso problema no resuelto, llamado el "problema de los puentes de Königsberg".

Un río con dos islas atraviesa la ciudad. Las islas están unidas, entre si y con las orillas, a través desiete puentes. El problema consistía en establecer un recorrido que pasara una y solo una vez por cada uno de los siete puentes, partiendo de cualquier punto y regresando al mismo lugar.

Para probar que no era posible, Euler sustituyó cada zona de partida por un punto y cada puente por un arco, creando así un grafo, el primer grafo, diseñado para resolver unproblema.

Mostrar que el problema no tiene solución equivale a mostrar que el grafo no puede ser recorrido según criterios determinados.

Problema genérico: dado un grafo (con múltiples líneas entre pares de puntos) encontrar un camino que recorra el grafo pasando por cada arista exactamente una vez.

Solución: El grafo debe ser conexo, y en cada punto deben incidir unnúmero par de líneas. Esta condición es suficiente para definir lo que se llama un ciclo euleriano.

A partir de Euler el modelado mediante grafos fue desarrollando esta metodología hasta convertirse en la actualidad, en una herrramienta de trabajo para ciencias tan diferentes como la Física, la Química, la Sicosociología, la Economía, la Lingüística, etc.

La teoría degrafos está íntimamente relacionada con varias ramas de la Matemáticas como por ejemplo la Teoría de Conjuntos, el Análisis Numérico, Probabilidad, Topología, etc. y es la base conceptual en el tratamiento de problemas combinatorios.

La eficacia de los grafos se basa en su gran poderío de abstracción y la muy clara representación de cualquier relación (de orden,precedencia, etc) lo que facilita enormemente tanto la fase de modelado como de resolución del problema. Gracias a la Teoría de Grafos se han desarrollado una gran variedad de algoritmos y métodos de resolución eficaces que nos permiten tomar una mejor decisión.

No se debe confundir el grafo con el sistema real al que está asociado. El grafo es una estructura que admitimos adecuada en loconcerniente a las propiedades que nos interesan, donde luego aplicamos las deducciones y reglas matemáticas para obtener datos y poder decidir.

Una aplicación frecuente de la teoría de grafos es la del método de camino hamiltoniano óptimo para decidir el camino a seguir por un cobrador, de tal modo de economizar sus energías, las suelas de sus zapatos y su bolsillo.

Elobjetivo es hallar un camino que pase por todas las casas una y solo una vez y que nos dé el costo menor en distancia. Dicho de otro modo, se deben buscar las permutaciones de las casas de forma tal que la distancia recorrida total sea mínima.
Se conoce la distancia entre cada par de casas, según si las calles son flechadas o no se orientarán o no las conexiones entre pares decasas.

Obsérvese que si se hicieran todas las permutaciones, suponiendo un caso muy reducido de diez casas, se tendrían más de 3 millones de permutaciones (10!).
Si cada casa es representada por un vértice y cada camino entre par de casas por una arista ponderada por la distancia mínima entre pares de casas, tendremos un grafo completo y simétrico (cuando no hay callesflechadas).

El problema se reduce entonces, a obtener un camino hamiltoniano óptimo. Todo algoritmo conocido para encontrar ciclos hamiltonianos requiere al menos un tiempo exponencial de cálculo, o factorial en el peor de los casos.

Otro ejemplo para el que grafos provee un natural modelo matemático:
Supongamos que el siguiente grafo representa una red de líneas...