Estructura de ciclos y vértices en Digrafos Fuertemente Conexos Minimales

Resumen

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 A de vértices del ciclo entonces contiene al menos A vértices lineales en el MSD; que dado un ciclo de longitud q contenido en el MSD, el número A de vértices lineales contenidos en el MSD satisface A > \_(q + 1)/2J; pero también, hemos demostrado que A 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 [7]; y finalmente, hemos demostrado que el cálculo del ciclo con longitud máxima en un MSD es un problema NP-Duro. ----------ABSTRACT---------- This work shows a study about the structure of the vertices and cycles contained in a Minimal Strong Digraph (MSD). The structure of a given cycle is determined by the strongly connected components (SC, strong components) that appear after suppressing the arcs of the cycle. By this process and by the contraction of all SC in a unique vertex we obtain a Hasse diagram that comes from the MSD. The cyclic structure of this family of digraphs can also be studied by analyzing the vertices that have a high in- or outdegree. Among other properties, we show that any SC conformed by more than one vertex (non trivial SC) has at least one linear vertex (a vertex with indegree and outdegree equal to 1) in the MSD; that in the Hasse diagram exists at least one linear vertex for each non-trivial maximal or minimal (here, non-trivial means that the vertex has at least one incident arc); that if an SC contains a number A of vertices of the cycle then contains at least A linear vertices in the MSD; that given a cycle of length q contained in the MSD, the number A of linear vertices contained in the MSD satisfies A > \_(q+1)/2J; but also, we have proved that A is lower bounded by the maximal in- or outdegree of any vertex of the MSD and that the maximal length of a cycle contained in an MSD is lesser than or equal to 2n — m where n,m are the order and the size of the MSD respectively; we have found a bound for the coefficients of the characteristic polynomial of an MSD, extending the result in [7]; and finally, we have proved that computing the longest cycle contained in an MSD is a NP-Hard problem.