Št. zadetkov: 7
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;delno urejena množica;temeljni graf;tetiven graf;razcepljen graf;bločni graf;mathematics;graph theory;poset;underlying graph;chordal graph;split graf;block graph;
Problem prepoznavanja grafov pokritij-neprimerljivosti (to je grafov, ki jih dobimo iz delno urejenih množic kot povezavno unijo njihovega grafa pokritij in grafa neprimerljivosti) je NP-poln v splošnem, kot so dokazali v [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparabilit ...
Leto:
2010
Vir:
Fakulteta za naravoslovje in matematiko (UM FNM)
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;delno urejena množica;temeljni graf;tranzitna funkcija;tetiven graf;razdaljno-hereditaren graf;mathematics;graph theory;poset;underlying graph;transit function;chordal graph;distance-hereditary graph;claw;
Vpeljemo graf pokritij-neprimerljivosti (ki mu na kratko rečemo CI-graf), katerega množica povezav je unija množic povezav grafa neprimerljivosti in grafa pokritja dane delno urejene množice. S pomočjo prepovedanih izometričnih delno urejenih podmnožic, okarakteriziramo tiste delno urejene množice, ...
Leto:
2008
Vir:
Fakulteta za elektrotehniko, računalništvo in informatiko (UM FERI)
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;n-arnost;tranzitna funkcija;vmesnost;Steinerjeva konveksnost;mathematics;graph theory;n-arity;transit function;betweenness;Steiner convexity;
Predstavljene so ▫$n$▫-arne tranzitne funkcije kot generalizacija binarnih (2-arnih) tranzitnih funkcij. Pokažemo, da so na naravni način povezane z konveksnostmi in predstavimo Stienerjevo konveksnost kot naravno ▫$n$▫-arno generalizacijo geodetske konveksnosti. Posplošimo tudi aksiome vmesnosti za ...
Leto:
2010
Vir:
Fakulteta za elektrotehniko, računalništvo in informatiko (UM FERI)
Izvirni znanstveni članek
Oznake:
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;
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 d ...
Leto:
2009
Vir:
Fakulteta za elektrotehniko, računalništvo in informatiko (UM FERI)
Izvirni znanstveni članek
Oznake:
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;
Koncept ▫$k$▫-Steinerjevih intervalov naravno posplošuje geodetske (binarne) intervale. Definiran je kot preslikava ▫$S: V\times \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 ...
Leto:
2009
Vir:
Fakulteta za naravoslovje in matematiko (UM FNM)
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;prepovedani podgrafi;inducirana pot;intervalna funkcija;aksiomi vmesnosti;tetivni grafi;razdaljno dedni grafi;mathematics;graph theory;forbidden subgraphs;induced path;interval function;betweenness axioms;chordal graphs;distance hereditary graphs;
Naj bo ▫$I_G(x,y)$▫ interval najkrajših ▫$x,y$▫-poti in ▫$J_G(x,y)$▫ interval induciranih ▫$x,y$▫-poti v povezanem grafu ▫$G$▫. Obravnavani so naslednji trije aksiomi vmesnosti za množico ▫$V$▫ in ▫$R: V \times V \rightarrow 2^V$▫: (i) ▫$x \in R(u,y), y \in R(x,v), x \neq y, |R(u,v)|>2 \Rightarrow x ...
Leto:
2013
Vir:
Fakulteta za elektrotehniko, računalništvo in informatiko (UM FERI)
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;Steinerjev interval;geodetski graf;vmesnost;mathematics;graph theory;Steiner interval;geodetic graph;betweenness;
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 ...
Leto:
2011
Vir:
Fakulteta za elektrotehniko, računalništvo in informatiko (UM FERI)