Aplicaciones de los grafos

Aplicaciones de los grafos.
Una de las aplicaciones de la teoría de grafos, como es la modelización de redes de interconexión, motivó la formulación de ciertos problemas de optimización discretos,entre ellos el problema grado/diámetro, y el consiguiente interés por el estudio de ciertas clases de dígrafos llamados denso, Contribuir a dicho estudio -en lo que atañe a cuestiones de existencia,enumeración y obtención de invariantes gráficos- utilizando básicamente herramientas algebraicas (espectrales) ha sido el objetivo principal de esta tesis.
El problema grado/diámetro para dígrafosconsiste en determinar el número máximo de vértices que puede tener un dígrafo fijados su grado máximo de salida y su diámetro. Se conoce una cota natural para dicho orden óptimo, llamado cota de Moore,la cual únicamente se alcanza para los dígrafos ciclos y los dígrafos completos. Esta limitación sugiere estudiar para qué valores del grado y diámetro existen dígrafos de orden próximo (una unidadmenos) a la inalcanzable cota, llamados dígrafos casi de Moore. Ello equivale a buscar matrices binarias que verifiquen una ecuación del tipo.
Donde J es la matriz toda de unos y P es una matriz depermutación que conmuta con A; es I + A + ....... + AK = J. P representa un automorifsmo del dígrafo que tiene a A como matriz de adyacencia. Relacionando el espectro de una posible solución A con laestructura cíclica de la permutación asociada a P, hemos deducido nuevas condiciones necesarias para la existencia de un digrafo casi de Moore y hemos concluido su enumeración para diámetro dos, en lacual nos ha aparecido la estructura de dígrafo línea como una propiedad extemal.
Otra de sus aplicaciones es la síntesis de circuitos secuenciales, contadores o sistemas de apertura. Además se utilizamucho para el diseño de trayectorias para hacer mas óptimos los caminos aplicando algoritmos como puede ser el algoritmo de Floyd.
Los grafos son importantes en el estudio de la biología y hábitat....