Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Repository of the University of Ljubljana
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Browse
New in RUL
About RUL
In numbers
Help
Sign in
Details
Problem Steinerjevega drevesa
ID
Prevc Mavrin, Darja
(
Author
),
ID
Cencelj, Matija
(
Mentor
)
More about this mentor...
,
ID
Gabrovšek, Boštjan
(
Comentor
)
URL - Presentation file, Visit
http://pefprints.pef.uni-lj.si/4587/
PDF - Presentation file,
Download
(1,39 MB)
MD5: 4A53085B2D174A03934F4C84B722F57E
Image galllery
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).
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
Views:
2022
Downloads:
343
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
PREVC MAVRIN, Darja, 2017,
Problem Steinerjevega drevesa
[online]. Master’s thesis. [Accessed 9 July 2025]. Retrieved from: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=eng&id=94158
Copy citation
Share:
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
Similar documents
Similar works from RUL:
Searching for similar works...
Similar works from other Slovenian collections:
Back