KARAKTERIZACIJA REDUCIBILNIH ŠESTKOTNIKOV ELEMENTARNIH BENZENOIDNIH GRAFOVČernel, Milan (Avtor) Taranenko, Andrej (Mentor) grafvrhdolinalicebenzenoidni graf1-faktorreducibilni šestkotnikdekompozicija reducibilnih licBenzenoidni graf je končen povezan v ravnino vložen graf brez presečnih vozlišč, v katerem je vsako lice omejeno s pravilnim šestkotnikom z dolžino stranice ena. Benzenoidni graf G je elementaren, če vsaka povezava pripada nekemu 1-faktorju grafa G. Šestkotnik h elementarnega benzenoidnega grafa je reducibilen, če tudi po odstranitvi mejnih povezav in vozlišč tega šestkotnika, graf ostane elementaren benzenoidni graf. Karakteriziramo reducibilne šestkotnike elementarnega benzenoidnega grafa. Karakterizacija je osnova za algoritem, s katerim se ugotovi zaporedje reducibilnih šestkotnikov, ki dekompozirajo graf iz te družine, v času O(n2). Poleg tega je predstavljen algoritem, ki dekompozira elementarni benzenoidni graf z največ eno perikondenzirano komponento v linearnem času.[M. Černel]20112011-05-04 13:44:24Diplomsko delo18256UDK: 51(043.2)COBISS_ID: 18406408NUK URN: URN:SI:UM:DK:AQECPZFUsl