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

Arcos Argudo, Miguel Arturo (2020). Estructura de ciclos y vértices en Digrafos Fuertemente Conexos Minimales. Thesis (Doctoral), E.T.S.I. de Sistemas Informáticos (UPM). https://doi.org/10.20868/UPM.thesis.63286.

Description

Title: Estructura de ciclos y vértices en Digrafos Fuertemente Conexos Minimales
Author/s:
  • Arcos Argudo, Miguel Arturo
Contributor/s:
  • García López de Lacalle, Jesús
  • Pozo Coronado, Luis
Item Type: Thesis (Doctoral)
Date: 2020
Subjects:
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Matemática Aplicada a las Tecnologías de la Información y las Comunicaciones
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only until 1 March 2021 - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (525kB)

Abstract

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.

More information

Item ID: 63286
DC Identifier: http://oa.upm.es/63286/
OAI Identifier: oai:oa.upm.es:63286
DOI: 10.20868/UPM.thesis.63286
Deposited by: Archivo Digital UPM 2
Deposited on: 31 Aug 2020 06:00
Last Modified: 31 Aug 2020 06:00
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM