2.
Algebra poti in dominantni problemi na grafovskih produktihPolona Pavlič, 2013, doktorska disertacija
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: 2779; Prenosov: 218
Celotno besedilo (1,51 MB)
