Št. zadetkov: 14
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;produkt grafov;klični separator;atom;mathematics;graph theory;clique separator;graph products;
Predstavljeni so vsi minimalni klični separatorji za vse štiri standardne produkte: kartezičnega, krepkega, leksikografskega in direktnega. Maksimalne atome natančno opišemo le za prve tri prej omenjene standardne produkte. V direktnem produktu maksimalne atome opišemo le delno. Tipična situacija za ...
Leto:
2012
Vir:
Fakulteta za elektrotehniko, računalništvo in informatiko (UM FERI)
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;medianski graf;kartezični produkt;periferija;periferna ekspanzija;mathematics;graph theory;median graph;Cartesian product;geodesic;periphery;peripheral expansion;
Graf periferij medianskega grafa je presečni graf njegovih perifernih podgrafov. V članku pokažemo, da je vsak graf brez univerzalnih vozlišč mogoče realizirati kot graf periferij nekega medianskega grafa. Karakteriziramo tiste medianske grafe, katerih graf periferij je spoj dveh grafov in pokažemo, ...
Leto:
2010
Vir:
Fakulteta za naravoslovje in matematiko (UM FNM)
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:
teorija grafov;leksikografski produkt;Steinerjeva konveksnost;Steinerjeva množica;Steinerjeva razdalja;graph theory;lexicographic product;Steiner convexity;Steiner set;Steiner distance;
The smallest tree that contains all vertices of a subset ▫$W$▫ of ▫$V(G)$▫ is called a Steiner tree. The number of edges of such a tree is the Steiner distance of ▫$W$▫ and union of all Steiner trees of ▫$W$▫ form a Steiner interval. Both of them are described for the lexicographic product in the pr ...
Leto:
2012
Vir:
Fakulteta za elektrotehniko, računalništvo in informatiko (UM FERI)
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;razdaljno uravnoteženi grafi;mathematics;graph theory;distance-balanced grapha;
A graph ▫$G$▫ is strongly distance-balanced if for every edge ▫$uv$▫ of ▫$G$▫ and every ▫$i \ge 0$▫ the number of vertices ▫$x$▫ with ▫$d(x,u) = d(x,v)-1 = i$▫ equals the number of vertices ▫$y$▫ with ▫$d(y,v) = d(y,u)-1 = i$▫. It is proved that the strong product of graphs is strongly distance-bala ...
Leto:
2008
Vir:
Fakulteta za elektrotehniko, računalništvo in informatiko (UM FERI)
Izvirni znanstveni članek
Oznake:
matematika;teorija grafov;problemi razmeščanja;medianske množice;antimedianske množice;konveksni podgrafi;mathematics;graph theory;facility location problems;median sets;antimedian sets;convex subgraphs;
Razdalja ▫$D_G(v)$▫ vozlišča ▫$v$▫ v grafu ▫$G$▫ je vsota razdalj med ▫$v$▫ in vsemi drugimi vozlišči grafa ▫$G$▫. Množica vozlišč grafa ▫$G$▫ z maksimalno (minimalno) razdaljo je antimedianska (medianska) množica grafa ▫$G$▫. Dokazano je, da za poljubna grafa ▫$G$▫ in ▫$J$▫ ter za poljubno naravno ...
Leto:
2010
Vir:
Fakulteta za naravoslovje in matematiko (UM FNM)
Ni določena
Oznake:
medianski graf;medianska množica;funkcija oddaljenosti;geodetsko število;periferna transverzala;median graph;median set;remoteness function;geodetic number;periphery transverzal;hypercube;
Periferna transverzala medianskega grafa ▫$G$▫ je vpeljana kot množica vozlišč, ki zadane vse periferije grafa $G$. S pomočjo tega koncepta so na dva različna načina karakterizirani medianski grafi z geodetskim številom 2. To so natanko tisti medianski grafi, ki vsebujejo periferno transverzalo moči ...
Leto:
2008
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)