Problem Steinerjevega drevesa

magistrsko delo

Darja Prevc (Author), Matija Cencelj (Mentor), Boštjan Gabrovšek (Co-mentor)

Abstract

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).

Keywords

evklidska ravnina;Steinerjeva točka;minimalno vpeto drevo;Steinerjevo razmerje;točni algoritem;aproksimativni algoritem;

Data

Language:	Slovenian
Year of publishing:	2017
Typology:	2.09 - Master's Thesis
Organization:	UL PEF - Faculty of Education
Publisher:	[D. Prevc Mavrin]
UDC:	51(043.3)
COBISS:	11655241
Views:	800
Downloads:	185
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	The Steiner tree problem
Secondary 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.
Secondary keywords:	mathematics;matematika;
File type:	application/pdf
Type (COBISS):	Master's thesis/paper
Thesis comment:	Univ. v Ljubljani, Pedagoška fak., Poučevanje - predmetno poučevanje matematike in računalništva
Pages:	62 str.
ID:	10850364