La aplicación del álgebra abstracta y las computadoras para la solución de problemas de caminos en redes orientadas

M.A. Murray-Lasso

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 RESCATAR UN 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 DEMATLAB. EL TEMA SE PRESTA PARA SEGUIRLO EXTENDIENDO Y DISEÑAR PROYECTOS EDUCATIVOS COMPUTARIZADOS PARA EL APRENDIZAJE DE TEMAS IMPORTANTESDEREDESCUYASAPLICACIONESSONMUYEXTENSAS.

Palabras clave


álgebra abstracta; matriz de conexión; MATLAB; caminos en redes; optimización en redes

Texto completo:

PDF