Akademska digitalna zbirka SLovenije - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
PDF
  • Recognizing generalized Sierpiński graphs
    Imrich, Wilfried ; Peterin, Iztok
    Naj bo ▫$H$▫ poljuben graf na množici vozlišč ▫$V(H)=[n_H]=\{1,\ldots,n_H\}$▫. Posplošen graf Sierpińskega ▫$S_H^n$▫, ▫$n\in \mathbb{N}$▫, je definiran na množici vozlišč ▫$[n_H]^n$▫. Različni ... vozlišči ▫$u =u_n \ldots u_1$▫ in ▫$v = v_n\ldots v_1$▫ sta sosedi, če obstaja tak ▫$h \in [n]$▫, da velja ▫$(a)$▫ ▫$u_t = v_t$▫, za ▫$t>h$▫, ▫$(b)$▫ ▫$u_h \ne v_h$▫ in ▫$u_hv_h\in E(H)$▫ in ▫$(c)$▫ ▫$u_t = v_h$▫ in ▫$v_t = u_h$▫ za ▫$t<h$▫. Če je ▫$H$▫ poln graf ▫$K_k$▫, potem govorimo o grafu Sierpińskega ▫$S_{k}^n$▫. Predstavljen je algoritem, ki prepozna grafe Sierpińskega ▫$S_{k}^n$▫ v času ▫$O(|V(S_{k}^n)|^{1+1/n})=O(|E(S_k^n)|)$▫. Za posplošene grafe Sierpińskega ▫$S_H^n$▫ je predstavljen polinomski algoritem v primeru, ko graf ▫$H$▫ pripada določenemu razredu grafov. Opišemo tudi kako prepoznamo bazni graf ▫$H$▫ iz poljubnega grafa ▫$S_H^n$▫.
    Vir: Applicable analysis and discrete mathematics. - ISSN 1452-8630 (Vol. 14, no. 1, 2020, str. 122-137)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2020
    Jezik - angleški
    COBISS.SI-ID - 13390595

    Povezava(-e):

    http://pefmath.etf.rs/vol14num1/AADM-Vol14-No1-122-137.pdf
    DOI

Vnos na polico