mariposas

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 lascomponentes 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 pretende rescata 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 en el lenguaje de MATLAB. El tema se presta para seguirlo extendiendo y diseñar proyectos educativos computarizados parael 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.
 
Abstract
The connection matrix of oriented graphs and a generalization introduced by Gondran and Minoux to solve a great variety of path problems, including various optimization problems (maximize or minimizelengths, minimum capacity, probability, etc.), ennumeration of paths, path counting, and connection. To achieve this the matrix components are treated as elements of an algebraic structure called semiring or diod (an extension of a monoid.) The possibilities of using MATLAB for handling the matrices are explored and listings of educational programs (not for production runs) are provided. Thepurpose is to rescue a topic which has not become very popular due, in the authors opinion, to the fact that the originators Gondran and Minoux (Ref. 3) have treated the topic in a very abstract manner, oriented to mathematicians and difficult to grasp by engineers. In this article the topics are treated informally and illustrative examples are given (something that Ref. 3 does not provide) in greatdetail as well as listings in the MATLAB language. The topic is ammenable to extensions and it is possible to design educational computerized projects for learning important network topics with very wide applications.
Keywords: Abstract algebra, connection matrix, MATLAB, paths in networks, network optimization.
 
Introducción
En la solución de ciertos problemas de redes que tienen que ver concaminos, 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 quemanejan arreglos.
 
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 definela matriz de conexión C (también llamada matriz asociada con la gráfica o matriz de adyacencia) como la matrizn×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...