diplomsko delo
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: |
2014 |
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
|
Št. ogledov: |
1041 |
Št. prenosov: |
55 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
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 |