| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 3 / 3
First pagePrevious page1Next pageLast page
1.
Characterizing posets for which their natural transit functions coincide
Boštjan Brešar, Manoj Changat, Sandi Klavžar, Joseph Mathews, Antony Mathews, Prasanth G. Narasimha-Shenoi, 2009, original scientific article

Abstract: Standardna tranzitna funkcija delno urejene množice ▫$P$▫ je funkcija ▫$T_P$▫, ki vsakemu paru primerljivih elementov priredi interval med njima, za neprimerljiva elementa ▫$x,y$▫ pa je ▫$T_P(x,y) = {x,y}$▫. Na tri načine, tudi s prepovedanimi delno urejenimi podmnožicami, okarakteriziramo tiste delno urejene množice, v katerih standardna tranzitna funkcija sovpada s tranzitno funkcijo najkrajših poti njenega grafa pokritij-neprimerljivosti.
Keywords: matematika, teorija grafov, tranzitna funkcija, rangirana delno urejena množica, temeljni graf, geodetski interval, interval induciranih poti, mathematics, graph theory, transit function, ranked poset, underlying graph, geodesic interval, induced-path interval
Published: 10.07.2015; Views: 537; Downloads: 64
URL Link to full text

2.
Steiner intervals, geodesic intervals, and betweenness
Boštjan Brešar, Manoj Changat, Joseph Mathews, Iztok Peterin, Prasanth G. Narasimha-Shenoi, Aleksandra Tepeh, 2009, original scientific article

Abstract: Koncept ▫$k$▫-Steinerjevih intervalov naravno posplošuje geodetske (binarne) intervale. Definiran je kot preslikava ▫$S: Vtimes cdots times V longrightarrow 2^V$▫, kjer je ▫$S(u_1, dots ,u_k)$▫ množica tistih vozlišč grafa ▫$G$▫, ki ležijo na kakem Steinerjevem drevesu glede na multimnožico ▫$W = {u_1, dots ,u_k}$▫ vozlišč iz ▫$G$▫. V tem članku za vsako naravno število ▫$k$▫ dokažemo karakterizacijo razreda tistih grafov, v katerih imajo vsi ▫$k$▫-Steinerjevi intervali t.i. lastnost unije, ki pravi, da ▫$S(u_1,ldots, u_k)$▫ sovpada z unijo geodetskih intervalov ▫$I(u_i,u_j)$▫ med vsemi pari vozlišč iz ▫$W$▫. Izkaže se, da tedaj, ko je ▫$k>3$▫, ta razred sovpada z razredom grafov, v katerih ▫$k$▫-Steinerjev interval zadošča aksiomu monotonosti(m), kot tudi z razredom grafov, v katerih ▫$k$▫-Steinerjev interval zadošča aksiomu (b2), ki sta pogoja iz teorije vmesnosti. In sicer preslikava ▫$S$▫ zadošča aksiomu (m), če iz ▫$x_1, dots ,x_k in S(u_1, dots ,u_k)$▫ sledi ▫$S(x_1, dots ,x_k) subseteq S(u_1, dots ,u_k)$▫; ter ▫$S$▫ zadošča (b2), če iz ▫$x in S(u_1,u_2, dots ,u_k)$▫ sledi ▫$S(x,u_2, dots ,u_k) subseteq S(u_1, dots ,u_k)$▫. V primeru ▫$k=3$▫ so ti trije razredi grafov različni in za razreda grafov, v katerih Steinerjev interval zadošča lastnosti unije oz. aksiomu monotonosti (m), dokažemo strukturni karakterizaciji. Prav tako predstavimo več delnih ugotovitev za razred grafov, v katerih 3-Steinerjev interval zadošča aksimu (b2), ki vodijo do domneve, da so to natanko tisti grafi, v katerih je vsak blok geodetski graf z diametrom 2.
Keywords: matematika, teorija grafov, Steinerjev interval, geodetski interval, razdalja, vmesnost, monotonost, bločni graf, mathematics, graph theory, Steiner interval, geodesic interval, distance, betweenness, monotonicity, block graph
Published: 10.07.2015; Views: 332; Downloads: 51
URL Link to full text

3.
A note on Steiner intervals and betweenness
Manoj Changat, Anandavally K. Lakshmikuttyamma, Joseph Mathews, Iztok Peterin, Prasanth G. Narasimha-Shenoi, Aleksandra Tepeh, 2011, original scientific article

Abstract: Geodetka in geodetski interval, ki je sestavljen iz vseh vozlišč, ki pripadajo kakšni geodetki med fiksnim parom vozlišč v povezanem grafu ▫$G$▫, sta sestavni del metrične teorije grafov. Prav tako je znano, da je Steinerjevo drevo (multi) množice s ▫$k$▫ (▫$k>2$▫) vozlišči, posplošitev geodetke. V (B. Brešar, M. Changat, J. Mathews, I. Peterin, P. G. Narasimha-Shenoi, A. Tepeh Horvat, Steiner intervals, geodesic intervals, and betweenness, Discrete Math. 309 (2009) 6114--6125) so se avtorji ukvarjali s ▫$k$▫-Steinerjevimi intervali ▫$S(u_{1},u_{2},ldots, u_{k})$▫ povezanih grafov (▫$k geq 3$▫) kot ▫$k$▫-arnimi posplošitvami geodetskih intervalov. Analogno sta bila iz binarne na ▫$k$▫-arno funkcijo posplošena tudi vmesnostni aksiom (b2) in monotoni aksiom(m) kot: za vsa vozlišča ▫$u_{1}, ldots, u_{k}, x, x_{1}, ldots, x_{k} in V(G)$▫, ki niso nujno različna ▫$$(b2)quad x in S(u_{1}, u_{2}, ldots, u_{k}) Rightarrow S(x, u_{2}, ldots, u_{k}) subseteq S(u_{1}, u_{2}, ldots, u_{k}),$$▫ ▫$$(m) quad x_{1}, ldots, x_{k} in S(u_{1}, ldots, u_{k})Rightarrow S(x_{1}, ldots,x_{k}) subseteq S(u_{1}, ldots, u_{k}).$$▫ Avtorji so v zgoraj omenjenem članku domnevali, da ▫$3$▫-Steinerjev interval povezanega grafa ▫$G$▫ zadošča vmesnostnemu aksiomu (b2) natanko tedaj, ko je vsak blok grafa ▫$G$▫ geodetski z diametrom največ 2. V tem delu dokažemo to domnevo. Pri tem dodatno dokažemo, da v vsakem geodetskem bloku z diametrom vsaj 3 obstaja izometrični cikel dolžine ▫$2k+1$▫, ▫$k>2$▫. Prav tako predstavimo dodaten aksiom (b2(2)), ki je smiseln le za 3-Steinerjeve intervale in pokažemo, da je le ta ekvivalenten monotonemu aksiomu.
Keywords: matematika, teorija grafov, Steinerjev interval, geodetski graf, vmesnost, mathematics, graph theory, Steiner interval, geodetic graph, betweenness
Published: 10.07.2015; Views: 374; Downloads: 47
URL Link to full text

Search done in 0.05 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica