La Aplicaci N Del Lgebra Abstracta Y Las Computadoras Para La Soluci N De Problemas De Caminos En Redes Orientadas
Páginas: 33 (8101 palabras)
Publicado: 24 de mayo de 2015
La aplicación del álgebra abstracta y las computadoras para la solución de problemas de caminos en redes orientadas
The Application of Abstract Algebra and Computers to the Solution of Path Problems in Oriented Networks
M.A. Murray–Lasso
División de Ingeniería Mecánica e Industrial. Programa de Posgrado en Ingeniería. Facultad de Ingeniería, Universidad Nacional Autónoma de México.E–mail: mamurraylasso@yahoo.com
Recibido: julio de 2006
Reevaluado: enero de 2008
Aceptado: agosto de 2009
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 pretende rescata run temaque 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 deMATLAB. 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.
Abstract
The connection matrix of oriented graphs and a generalization introduced by Gondran and Minoux to solve agreat variety of path problems, including various optimization problems (maximize or minimize lengths, 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 areexplored and listings of educational programs (not for production runs) are provided. The purpose 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 treatedinformally and illustrative examples are given (something that Ref. 3 does not provide) in great detail 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, networkoptimization.
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 decaminos en redes. Los algoritmos resultantes son fáciles de automatizar en lenguajes que manejan 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...
The Application of Abstract Algebra and Computers to the Solution of Path Problems in Oriented Networks
M.A. Murray–Lasso
División de Ingeniería Mecánica e Industrial. Programa de Posgrado en Ingeniería. Facultad de Ingeniería, Universidad Nacional Autónoma de México.E–mail: mamurraylasso@yahoo.com
Recibido: julio de 2006
Reevaluado: enero de 2008
Aceptado: agosto de 2009
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 pretende rescata run temaque 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 deMATLAB. 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.
Abstract
The connection matrix of oriented graphs and a generalization introduced by Gondran and Minoux to solve agreat variety of path problems, including various optimization problems (maximize or minimize lengths, 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 areexplored and listings of educational programs (not for production runs) are provided. The purpose 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 treatedinformally and illustrative examples are given (something that Ref. 3 does not provide) in great detail 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, networkoptimization.
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 decaminos en redes. Los algoritmos resultantes son fáciles de automatizar en lenguajes que manejan 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...
Leer documento completo
Regístrate para leer el documento completo.