diplomsko delo
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: |
2014 |
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
|
Views: |
1041 |
Downloads: |
55 |
Average score: |
0 (0 votes) |
Metadata: |
|
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 |