2026-05-05T19:20:52Zhttps://uvadoc.uva.es/oai/requestoai:uvadoc.uva.es:10324/612162023-09-26T13:16:03Zcom_10324_38col_10324_852
Obtención del mínimo árbol expandido en el problema de Steiner Euclídeo
Díez Parra, Gonzalo
Mata Crespo, Raquel
Se analizará el problema de Steiner Euclídeo con el objetivo de buscar el
mínimo árbol expandido que conecte un conjunto finito de puntos del plano
euclídeo. Se representarán gráficamente los árboles de Steiner en el contexto
de grafos no dirigidos y con pesos ponderados en sus aristas.
Se estudiará la modelización del problema de Steiner como un diseño de redes
con costes fijos y, para ejemplificar la resolución manual del problema de
Steiner, se expondrán algunos ejemplos relativamente sencillos para su
implementación con intención de poder aplicarse en problemas de mayor
complejidad que requieran cierta dificultad y rapidez computacional.
Se comentará también la versión con distancias rectilíneas donde las
conexiones estarán restringidas, sólo podrán ser horizontales o verticales.
The Euclidean Steiner problem will be analyzed in order to find the minimum
expanded tree that connects a finite set of points in the Euclidean plane. Steiner
trees will be represented graphically in the context of undirected graphs and
with weighted weights on their edges.
The modeling of the Steiner problem will be studied as a design of networks
with fixed costs and, to exemplify the manual resolution of the Steiner problem,
some relatively simple examples will be presented for its implementation with
the intention of being able to apply it to more complex problems that require
some difficulty. and computational speed.
The version with rectilinear distances will also be commented where the
connections will be restricted, they can only be horizontal or vertical.
2023
info:eu-repo/semantics/bachelorThesis
spa
Departamento de Estadística e Investigación Operativa
https://uvadoc.uva.es/handle/10324/61216
https://uvadoc.uva.es/bitstream/10324/61216/3/license.txt
289d98c1665ee0d20312360f0e8643c8
https://uvadoc.uva.es/bitstream/10324/61216/1/TFG-I-2651.pdf
c3b0171cf51b5b7d94110e132fa68e2f
Attribution-NonCommercial-NoDerivatives 4.0 Internacional