Estructura de los ciclos en los Minimal Strong Digraphs

Arcos Argudo, Miguel (2017). Estructura de los ciclos en los Minimal Strong Digraphs. Tesis (Master), E.T.S.I. de Sistemas Informáticos (UPM).

Descripción

Título: Estructura de los ciclos en los Minimal Strong Digraphs
Autor/es:
  • Arcos Argudo, Miguel
Director/es:
  • García López de Lacalle, Jesús
  • Pozo Coronado, Luis
Tipo de Documento: Tesis (Master)
Título del máster: Ciencias y Tecnologías de la Computación
Fecha: Abril 2017
Materias:
Escuela: E.T.S.I. de Sistemas Informáticos (UPM)
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (510kB) | Vista Previa

Resumen

El estudio de grafos dentro de las Ciencias de la Computación ha permitido resolver problemas de distinta naturaleza. Los algoritmos que se han generado inspirados en este campo han permitido optimizar procesos en varias industrias y reducir costes de manera muy significativa. Un tipo de grafo, cuyo estudio aún tiene mucho por descubrir, ha sido denominado Minimal Strong Digraph (MSD). Su estructura permite interconectar todos sus vértices mediante caminos dirigidos utilizando una cantidad mínima de aristas. Las propiedades de los MSD permiten establecer una interesante comparativa con los árboles, debido a la similitud que se puede encontrar entre estos dos tipos de grafos. Los grafos llamados “ciclos” pertenecen a la familia de los MSD, y constituyen uno de los componentes más importantes, pues se ha demostrado que toda arista en un MSD debe pertenecer al menos a un ciclo. La investigación ejecutada en este trabajo consiste en el análisis de las configuraciones de los ciclos contenidos en un MSD para lo que se ha utilizado algoritmos de simulación, y en base a los resultados obtenidos con la ejecución de los algoritmos se han descubierto y demostrado matemáticamente nuevas propiedades de los MSD. Se demuestra que la cantidad de componentes fuertemente conexas (CFC) asociadas a los vértices de un ciclo, así como la cantidad de vértices contenidos en una misma CFC, dependen de la longitud del ciclo. Además se demuestra de manera general varias configuraciones de las CFC asociadas a los vértices de un ciclo en las que debe existir al menos un vértice lineal por cada CFC. ABSTRACT The study of graphs in Computer Science has allowed solving problems of different nature. The algorithms that have been generated inspired in graphs have allowed to optimize processes in several industries and to reduce costs significantly. A type of graph, whose study has much to discover, has been named Minimal Strong Digraph (MSD). Its structure allows interconnecting all its vertexes through directed paths using a minimum amount of edges. The MSD's properties allow establishing an interesting comparison with the trees, due to the similarity that can be found between these two types of graphs. Graphs named "cycles" belong to MSD's family, and, are one of the most important components, as it has been shown that every edge in an MSD must belong to at least one cycle. The research carried out in this work consists of the analysis of the configurations of the cycles contained in an MSD for which simulation algorithms have been used, and based on the results obtained with the execution of the algorithms have been demonstrated new MSD's properties. It is concluded that the number of strongly connected components (CFC) associated with the vertexes of a cycle, as well as the number of vertexes contained in the same CFC, depend on the length of the cycle. In addition, it is generally demonstrated several CFC configurations associated to the vertexes of a cycle in which there must exist at least one linear vertex by CFC.

Más información

ID de Registro: 47457
Identificador DC: http://oa.upm.es/47457/
Identificador OAI: oai:oa.upm.es:47457
Depositado por: Biblioteca Universitaria Campus Sur
Depositado el: 29 Ago 2017 08:38
Ultima Modificación: 29 Ago 2017 08:38
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM