Problem Steinerjevega drevesa

Prevc Mavrin, Darja (author), Cencelj, Matija (mentor), Gabrovšek, Boštjan (co-mentor)

S problemom Steinerjevega drevesa se je ukvarjalo veliko število matematikov. Steinerjevo drevo je poimenovano po švicarskem matematiku Jakobu Steinerju (1796-1863), čeprav ni jasno, kakšen je bil sploh njegov prispevek k temu problemu. Problem Steinerjevega drevesa je iskanje najkrajše mreže s fiksnim številom točk v ravnini (osredotočili se bomo na evklidsko), pri čemer lahko dodajamo točke, ki omogočajo minimizacijo celotne dolžine drevesa. Te točke imenujemo Steinerjeve točke. Razmerje med dolžino Steinerjevega drevesa in dolžino minimalnega vpetega drevesa predstavlja Steinerjevo razmerje. V magistrskem delu bomo predstavili lastnosti Steinerjevega drevesa in točne ter aproksimativne algoritme, ki se uporabljajo za reševanje problema Steinerjevega drevesa. Obdelali bomo primere Steinerjevega drevesa za tri oziroma štiri terminale, ki so odvisni od postavitve terminalov v ravnini. Problem Steinerjevega drevesa ni uporaben le v matematičnem smislu, ampak tudi v realnem življenju (na primer v prometni infrastrukturi).

• Language: Slovenian
• Keywords: evklidska ravnina
• Work type: Master's thesis/paper
• Typology: 2.09 - Master's Thesis
• Organization: PEF - Faculty of Education
• Year: 2017
• PID: 20.500.12556/RUL-94158
• COBISS.SI-ID: 11655241
• Publication date in RUL: 23.08.2017

Secondary language

• Language: English
• Title: The Steiner tree problem

Abstract

The Steiner tree problem, named after a Swiss mathematician Jacob Steiner (1796–1863), is a problem that many mathematicians have been dealing with. His contribution, however, is unclear even to this day. The Steiner tree problem is searching for the shortest network with fixed number of points in the plane (this thesis focuses on the Euclidean plane), where points, which enable minimisation of the total length of the tree, can be added. These points are called the Steiner points. The Steiner ratio is the ratio between the length of the Steiner tree and the length of the minimal spanning tree. This thesis explanes the features of the Steiner tree and the exact and approximation algorithm used to solve the Steiner tree problem. Furthermore, it deals with the cases of the Steiner tree for three or four terminals, which are dependent on the positions of the terminals in the plane. The Steiner tree problem is not useful only in the mathematical world, but it can be also applied in the real world. For example, the traffic infrastructure.

• Keywords: Euclidean plane