Problem Steinerjevega drevesa

magistrsko delo

Darja Prevc (Avtor), Matija Cencelj (Mentor), Boštjan Gabrovšek (Komentor)

Povzetek

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

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2017
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UL PEF - Pedagoška fakulteta
Založnik:	[D. Prevc Mavrin]
UDK:	51(043.3)
COBISS:	11655241
Št. ogledov:	800
Št. prenosov:	185
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	The Steiner tree problem
Sekundarni povzetek:	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.
Sekundarne ključne besede:	mathematics;matematika;
Vrsta datoteke:	application/pdf
Vrsta dela (COBISS):	Magistrsko delo/naloga
Komentar na gradivo:	Univ. v Ljubljani, Pedagoška fak., Poučevanje - predmetno poučevanje matematike in računalništva
Strani:	62 str.
ID:	10850364