Resumen de Estructura de ciclos y vértices en digrafos fuertemente conexos minimales
Miguel Arcos Argudo
Este trabajo muestra un estudio sobre la estructura de los ciclos contenidos en un Minimal Strong Digraph (MSD). La estructura de un ciclo dado está determinada por las componentes fuertemente conexas (strong components, o SC) que aparecen después de eliminar los arcos del ciclo. Mediante este proceso y mediante la contracción de todas las SC en un único vértice obtenemos un diagrama de Hasse que proviene del MSD. La estructura cíclica de esta familia de digrafos también puede estudiarse mediante el análisis de los vértices que tienen un alto grado de entrada o salida. Entre otras propiedades, demostramos que cualquier SC conformada por más de un vértice (SC no trivial) tiene al menos un vértice lineal (un vértice con grado de entrada y grado de salida igual a 1) en el MSD; que en el diagrama de Hasse existe al menos un vértice lineal por cada maximal (minimal) no trivial (vértice con al menos un arco incidente); que si una SC contiene un número λ de vértices del ciclo entonces contiene al menos λ vértices lineales en el MSD; que dado un ciclo de longitud q contenido en el MSD, el número λ de vértices lineales contenidos en el MSD satisface λ≥⌊(q+1)/2⌋; pero también, hemos demostrado que λ está acotado inferiormente por el grado máximo de entrada (o de salida) de cualquier vértice del MSD y que la máxima longitud de un ciclo contenido en el MSD es menor o igual a 2n-m, donde n, m son el orden y el tamaño del MSD respectivamente; hemos encontrado una cota para los coeficientes del polinomio característico de un MSD, extendiendo el resultado presentado en trabajos anteriores; y finalmente, hemos demostrado que el cálculo del ciclo con longitud máxima en un MSD es un problema NP-Duro.
