Iskanje po katalogu digitalne knjižnice

Opis: Z uporabo algebraičnega pristopa implementiramo konstantni algoritem za računanje dominantnega števila kartezičnih produktov poti in ciklov. Podamo formule za dominantna števila ▫$gamma(P_n Box C_k)$▫ (za ▫$k leq 11$▫, ▫$n in {mathbb N}$)▫ in dominantna števila ▫$gamma(C_n Box P_k)$▫ in ▫$gamma(C_n Box C_k)$▫ (za ▫$k leq 6$▫, ▫$n in {mathbb N}$▫).
Ključne besede: teorija grafov, kartezični produkt, grid, torus, dominacija, algebra poti, konstantni algoritem, graph theory, Cartesian product, grid graph, torus, graph domination, path algebra, constant time algorithm
Objavljeno v DKUM: 10.07.2015; Ogledov: 1740; Prenosov: 40
Povezava na celotno besedilo

Opis: Različni problemi grafovskih invariant predstavljajo velik del študij na področju teorije grafov. Ker so ti problemi v veliki meri NP-polni, je smiselno iskati rešitve na določenih zanimivih družinah grafov. V tem delu se omejimo na probleme dominacije na družini poligrafov. To so grafi, ki izhajajo iz kemijske teorije grafov in so matematični model kemijske strukture polimera. V kemiji je polimer makromolekula, ki ima posebno ponavljajočo se strukturo molekul, povezanih s kovalentnimi vezmi. Mi se posebej omejimo na primere, ko so te ponavljajoče enote enake, oziroma v jeziku teorije grafov, ko so monografi izomorfni, ter so povezave med njimi enake. Taki grafi se imenujejo rotagrafi, če pa med prvim in zadnjim monografom ni povezav, imenujemo tak poligraf fasciagraf. S pomočjo algebre poti pokažemo, da se različni problemi dominacije na razredu poligrafov za fiksno velikost monografa lahko rešijo v konstantnem času. Ker so posebni primeri poligrafov tudi grafovski produkti poti in ciklov, za kartezični in direktni produkt implementiramo algoritem in dobimo formule za dominantna, neodvisna dominantna ter rimska dominantna števila teh grafov, kjer je eden od faktorjev fiksen. Nadalje pokažemo, da se preučevane grafovske invariante na fasciagrafih in rotagrafih, pri katerih je monograf enak, lahko razlikujejo le za konstantno vrednost, natančneje, za končno število (različnih) konstant. Nazadnje še rešimo problem rimskega dominantnega števila na leksikografskem produktu grafov. Z vpeljavo koncepta tako imenovanih dominatnih parov za poljubna grafa podamo formulo, ki določi rimsko dominantno število njunega leksikografskega produkta. Podamo tudi nove neskončne družine rimskih grafov.
Ključne besede: grafovski produkt, dominacija, algebra poti, konstantni algoritem, mreža, torus
Objavljeno v DKUM: 04.04.2013; Ogledov: 2780; Prenosov: 221
Celotno besedilo (1,51 MB)