diplomsko delo
Matija Pačnik (Author), Aleksander Vesel (Mentor)

Abstract

V diplomskem delu je predstavljen algoritem, ki poišče 4-tlakovanje elementarnega benzenoidnega grafa v linearnem času. Najprej so predstavljeni osnovni pojmi in definicije elementarnih benzenoidnih grafov. Pokazano je, da periferni 1 faktor elementarnega benzenoidnega grafa G inducira 4- tlakovanje od G. Predstavljen je algoritem MSH, ki poišče 1 faktor v linearnem času. Sledi razlaga algoritma RFD, ki se uporabi za dekompozicijo reducibilnih lic elementarnega benzenoidnega grafa. Delovanje obeh algoritmov je prikazano na primerih. V zadnjem poglavju so predstavljene programske rešitve, ki so bile uporabljene pri izdelavi spletne aplikacije in njeno delovanje na primerih različnih grafov.

Keywords

diplomska dela;benzenoidni grafi;4-tlakovanje;reducibilni šestkotniki;1-faktor;algoritem RFD;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
Publisher: [M. Pačnik]
UDC: 519.17(043.2)
COBISS: 21025800 Link will open in a new window
Views: 1041
Downloads: 55
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Web application for 4-tilings of benzenoid graphs
Secondary abstract: In this graduation thesis we present an algorithm that finds a 4-tiling of an elementary benzenoid graphs in linear time. First, we present basic terms and definitions of elementary benzenoid graphs. It is shown that a peripheral 1 factor of elementary benzenoid graph G induces 4-tilings of G. We present algorithm MSH, which finds 1 factor in linear time. Later we explain algorithm RFD which is used for reducible face decomposition of an elementary benzenoid graph. The running of both algorithms is shown by examples. The last chapter covers the software solutions that have been used in making of web application with detailed explanation by examples.
Secondary keywords: benzenoid graphs;1–factor;4–tiling;algorithm RFD;reducible hexagons;reducible face decomposition;
URN: URN:SI:UM:
Type (COBISS): Undergraduate thesis
Thesis comment: Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Pages: IX, 65 f.
ID: 8700789