Árbol generador euclídeo de longitud y diámetros cortos

Ruiz Rodríguez, Inés (2016). Árbol generador euclídeo de longitud y diámetros cortos. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Descripción

Título: Árbol generador euclídeo de longitud y diámetros cortos
Autor/es:
  • Ruiz Rodríguez, Inés
Director/es:
  • Abellanas Oar, Manuel
Tipo de Documento: Proyecto Fin de Carrera/Grado
Grado: Grado en Matemáticas e Informática
Fecha: Junio 2016
Materias:
Escuela: E.T.S. de Ingenieros 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 (918kB) | Vista Previa

Resumen

En este trabajo se plantea el problema de conectar n puntos del plano mediante un grafo conexo que tenga tanto su longitud como su diámetro lo más peque~nos posible. Se consideran grafos geométricos cuyos vértices son puntos del plano y cuyas aristas son segmentos rectilíneos que tienen por extremos dos vértices. La longitud de un grafo es la suma de las longitudes de sus aristas. La distancia entre dos vértices del grafo es la suma de las longitudes de las aristas del camino más corto que los conecta. El diámetro de un grafo es la mayor de las distancias entre dos de sus vértices. Está claro que el grafo de longitud mínima que conecta n puntos no contiene ciclos y, por tanto, se trata de un árbol. Si solo se considera esta condición, la solución la da el árbol generador euclídeo mínimo (EMST, Euclidean Minimum Spanning Tree en inglés). Sin embargo, el diámetro del EMST, como se verá en la memoria, puede ser muy grande. Por otra parte, si solo se considera la condición del diámetro mínimo, la solución será el árbol generador de diámetro mínimo (MDST, Minimum Diameter Spanning Tree en inglés) del que se conocen, como en el caso del EMST, algoritmos eficientes para su cálculo. Este cómputo se desarrollará en SAGE, un entorno de cálculos matemáticos (MCE { Mathematics computing enviroment) de código abierto, y usará una estructura para definir grafos planos llamada DCEL (lista de aristas doblemente enlazada). Al combinar las dos condiciones se plantea un problema de minimización biparamé trico para el que no se conocen soluciones. De hecho, no puede decirse que exista una solución óptima pues cada uno de estos criterios puede perjudicar al otro. En el trabajo se empieza haciendo un estudio estadístico del diámetro del EMST de conjuntos aleatorios de puntos que confirma que, en general, el EMST no es el árbol de diámetro mínimo que conecta los puntos. A continuación, se emplea la triangulación de Delaunay y algunos de sus subgrafos notables - el grafo de Gabriel y el de vecindad relativa (RNG, Relative Neighbour Graph en inglés)- como técnica para buscar una solución de equilibrio entre longitud y diámetro cortos. La técnica consiste en calcular, para los mencionados grafos, el árbol generador de diámetro mínimo. Se completa el trabajo con el análisis experimental de las soluciones propuestas.---ABSTRACT---This work presents the problem of connecting n points in the plane by a connected graph that has both its length and diameter as small as possible. Geometric graphs whose vertices are points in the plane and whose edges are rectilinear segments connecting vertices are considered. The length of a graph is the sum of the lengths of all edges. The distance between two vertices is the length of their shortest path in the graph. The diameter is the longest distance between any two vertices in the graph. It is clear that the graph of minimum length that connects n points does not contain cycles and, therefore, is a tree. If only this condition is considered, the solution to the problem is given by Euclidean Minimum Spanning Tree (EMST). However, the diameter of EMST, as will be seen in the work, can be very large. Moreover, if only the condition of minimum diameter is considered, the solution would be the Minimum Diameter Spanning Tree (MDST) for which eficient algorithms that compute it are known, similar to the EMST case. This operation will be carried out in SAGE, a free open source Mathematics computing enviroment (MCE), and it will use a DCEL (Doubly Connected Edge List) structure to define planar graphs. Combining the two conditions mentioned, a biparametric minimization problem with no known solutions arises. In fact, it cannot be stated that there exists an optimal solution, since the individual growth of one parameter may harm the other. This work begins performing a statistical study about the diameter of EMST with random point sets that confirms that, generally, EMST is not the minimum diameter tree. Then, it uses the Delaunay Triangulation and some of its important subgraphs - the Gabriel Graph and the Relative Neighbour Graph (RNG) - as a technique to find a balanced solution between short length and short diameter. The procedure involves calculating, for the above graphs, the Minimum Diameter Spanning Tree. To conclude, it presents experimental tests of the proposed solutions.

Más información

ID de Registro: 42904
Identificador DC: http://oa.upm.es/42904/
Identificador OAI: oai:oa.upm.es:42904
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 18 Jul 2016 08:06
Ultima Modificación: 27 Oct 2016 07:53
  • 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