Steinerova stabla

master's thesis

• Title (english): Steiner trees
• Author: Fran Vojković
• Mentor: Robert Manger (mentor)
• Committee member: Robert Manger (predsjednik povjerenstva)
• Committee member: Mladen Jurak (član povjerenstva)
• Committee member: Matej Mihelčić (član povjerenstva)
• Committee member: Juraj Šiftar (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2021-12-01, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu promatramo Steinerova stabla. Uvodno, iskazana je ukratko teorija grafova i neki rezultati iz teorije grafova potrebni za daljnje razmatranje Steinerovih stabla. Najprije promatramo Steinerova stabla u Euklidskom prostoru. Početno je iskazan Fermatov problem kao motivacija za proučavanje Steinerovih stabla te su dane dvije metode koje rješavaju Fermatov problem. Pomoću rješenja Fermatovog problema dolazimo i do prvog algoritma za Steinerov Euklidski problem. Dodatno iskazan je i numerički algoritam koji rješava Steinerov problem u Euklidskom prostoru. Posljednje proučavamo i Steinerov problem u mrežama. Navedeni su algoritmi za egzaktno i približno rješenje Steinerovog problema u mrežama.

Abstract (english)

In this thesis, we observe Steiner trees. In the introduction, we present fundamentals of graph theory and some results from graph theory required for further consideration of Steiner trees. Firstly, we observe Steiner’s trees in Euclidean space. Fermat’s problem is initially presented as a motivation for studying Steiner trees and two methods are given that solve Fermat’s problem. Using the solution of Fermat’s problem, we arrive at the first algorithm for Steiner’s Euclidean problem. The numerical algorithm that solves the Steiner problem in Euclidean space is additionally presented. Lastly, we also study Steiner’s problem in networks. Algorithms for the exact and approximate solution of the Steiner problem in networks are given.

• Keywords: teorija grafova; Euklidski prostor; Fermatov problem; Steinerov problem u mrežama
• Keywords (english): graph theory; Euclidean space; Fermat's problem; Steiner's problem in networks
• Language: croatian
• URN:NBN: urn:nbn:hr:217:999733
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access; Embargo expiration date: 2022-12-17
• Created on: 2021-12-17 12:49:59