bachiller

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 estan unidas, entre si
y con las orillas, a través de siete
puentes. El problemaconsistí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 un problema.
Mostrar que el problema no tiene solución equivale amostrar
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 se conexo, y en cada punto deben incidir un número par de
líneas. Esta condición es suficiente para definir lo que se llama un cicloeuleriano.
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 de grafos está íntimamente relacionada con varias ramas de la
Matemáticas como por ejemplo la Teoría de Conjuntos, elAná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, precendencia, etc) lo que facilita
enormemente tanto la fase de modelado como de resolución del problema. Gracias a
la Teoría de Grafos se handesarrollado 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 lo concerniente a las propiedades que nos
A
B
D
CIntroducción a la Investigación de Operaciones
56
interesan, donde luego aplicamos lasdeducciones 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.
El objetivo es hallar un camino que pase por todos las casas una y solo una vez y que
nos de el costo menoren 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 de casas.
Obsérvese que si se hicieran todas las permutaciones, suponiendo
un caso muy reducido de diez casas, se tendríanmá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 calles flechadas).
El problema se reduce entonces, a obtener un camino hamiltoniano óptimo. Todo
algoritmo conocido para encontrar cicloshamiltonianos 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 de teléfonos (o de
comunicaciones). Estamos interesados en la vulnerabilidad respecto a interrupciones
accidentales.
Problema 1: identificar esas líneas y centros
de...