Ingenieria

La aplicación del álgebra abstracta y las computadoras para la solución de problemas de caminos en redes orientadas
 
Resumen
Se presenta la matriz de conexión de gráficas orientadas y una generalización introducida por Gondran y Minoux para resolver una gran variedad de problemas de caminos, incluyendo diversos problemas de optimización (maximizar o minimizar longitudes, capacidad mínima,probabilidad, etc.), enumeración de caminos, cuenta de caminos, y conexión. Para lograr lo anterior, se tratan a las componentes de las matrices como elementos de una estructura algebraica llamada semianillo o dioide (extensión de un monoide). Se explora la posibilidad de utilizar MATLAB en el manejo de matrices y se dan listados de programas cuyo objetivo es educativo y no de producción. Se pretenderescata run tema que no se ha popularizado debido, en la opinión del autor, a que los originadores Gondran y Minoux (1984) han tratado el tema en forma muy abstracta, orientado a matemáticos y difícil de captar por ingenieros. En este artículo se tratan los temas informalmente y se dan ejemplos ilustrativos (cosa que Gondran y Minoux, no proveen en gran detalle), así como listados de programas enel lenguaje de MATLAB. El tema se presta para seguirlo extendiendo y diseñar proyectos educativos computarizados para el aprendizaje de temas importantes de redes cuyas aplicaciones son muy extensas.
Descriptores: álgebra abstracta, matriz de conexión, MATLAB, caminos en redes, optimización en redes.
 
Introducción
En la solución de ciertos problemas de redes que tienen que ver con caminos,la matriz de conexión generalizada juega un papel central. Si los problemas se plantean adecuadamente, algunos algoritmos clásicos como los de Jacobi y Gauss–Seidel para resolver sistemas lineales de ecuaciones por iteración, pueden utilizarse para resolver una variedad muy grande de problemas de caminos en redes. Los algoritmos resultantes son fáciles de automatizar en lenguajes que manejanarreglos.
 

La matriz de conexión y su generalización
Sea G una gráfica orientada con n nodos, cada par (i, j) de los cuales están conectados en un sentido por, a lo más, una sola rama, a la cual se le da un peso cij. Se admiten conexiones entre un nodo y sí mismo. (Los pesos son números reales que se pueden interpretar como longitudes, capacidades, confiabilidades, etcétera). Se define la matrizde conexión C (también llamada matriz asociada con la gráfica o matriz de adyacencia) como la matriz n×n que tiene como componentes cij, i = 1, 2,... ,n. (Bellman et al., 1970 y Mayeda, 1972). Cuando no existe conexión entre un par de nodos (o de un nodo con sí mismo) se pone un peso de cero. (Estamos pensando en pesos interpretados como capacidades; en caso de que fueran longitudes, se pondríaninfinitos que como veremos más adelante juegan un papel similar al cero para las operaciones que se utilizarán al generalizar el concepto de matriz de conexión.)
Por ejemplo, para la gráfica de la figura 1 con los pesos indicados junto a las ramas se tendría la matriz C que se muestra en la figura 1.

Una primera generalización de la matriz de conexión C se puede hacer admitiendo más de una ramaen paralelo en la misma dirección entre dos nodos o de un nodo con sí mismo. En este caso, simplemente se suman los pesos de las ramas en paralelo. (De nuevo estamos pensando en la interpretación de capacidad para los pesos, con otras interpretaciones se aplican otras operaciones.) Para la gráfica de la figura 2 su matriz de conexión generalizada es la que se muestra en la propia figura.

Unageneralización adicional que se le puede hacer a la matriz de conexión, consiste en que, en vez que los pesos de las componentes sean números reales, se les suponga elementos de un conjunto más amplio que permite la posibilidad de ser manipulado con operaciones como max, min, (unión), © (concatenación), y otros. Para muchos de los problemas que nos interesan, basta que los elementos sean miembros...