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

Povzetek

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.

Ključne besede

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

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
Založnik: [M. Pačnik]
UDK: 519.17(043.2)
COBISS: 21025800 Povezava se bo odprla v novem oknu
Št. ogledov: 1041
Št. prenosov: 55
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Web application for 4-tilings of benzenoid graphs
Sekundarni povzetek: 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.
Sekundarne ključne besede: benzenoid graphs;1–factor;4–tiling;algorithm RFD;reducible hexagons;reducible face decomposition;
URN: URN:SI:UM:
Vrsta dela (COBISS): Diplomsko delo
Komentar na gradivo: Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani: IX, 65 f.
ID: 8700789