Obtención del mínimo árbol expandido en el problema de Steiner Euclídeo

Abstract

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.