The Application of Abstract Algebra and Computers to the Solution of Path Problems in Oriented Networks

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 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 USINGMATLAB FOR HANDLING THE MATRICES ARE EXPLORED 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 TREATED INFORMALLY 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.