Aplicaciones de la teoría espectral al estudio de los digrafos densos

• Autores: Joan Gimbert Quintilla
• Directores de la Tesis: Miguel Ángel Fiol Mora (dir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2000
• Idioma: español
• Tribunal Calificador de la Tesis: José Luis Andrés Yebra (presid.) , Ernest Garriga Valle (secret.) , Josep Maria Miret Biosca (voc.) , Mirka Miller (voc.) , Enric Ventura i Capell (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • 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 digrafos 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.

    Para ello hemos traducido las cuestiones anteriores en términos matriciales y aritméticos.

    El problema grado/diámetro para digrafos consiste en determinar el número máximo de vértices que puede tener un digrafo fijados su grado máximo de salida y su diámetro. Se conoce una cota natural para dicho orden óptimo, llamda cota de Moore, la cual únicamente se alcanza para los digrafos ciclos y los digrafos completos. Esta limitación sugiere estudiar para qué valores del grado y diámetro existen digrafos de orden próximo (una unidad menos) a la inalcanzable cota, llamados digrafos 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 de permutación que conmuta con A; es I + A + ....... + AK = J Decir, P representa una utomorifsmo del digrafo que tiene a A como matriz de adyacencia. Relacionando el espectro de una posible solución A con la estructura 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 la cual nos ha aparecido la estructura de digrafo línea como una propiedad extemal.

    A raíz de este hecho hemos estudiado para qué ecuaciones matriciales y polinómicas del tipo puede asegurarse que todas sus (0,1) soluciones corresponden a digrafos línea.

    A' p(A)=