| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


51 - 60 / 97
Na začetekNa prejšnjo stran12345678910Na naslednjo stranNa konec
51.
Steiner intervals, geodesic intervals, and betweenness
Boštjan Brešar, Manoj Changat, Joseph Mathews, Iztok Peterin, Prasanth G. Narasimha-Shenoi, Aleksandra Tepeh, 2009, izvirni znanstveni članek

Opis: 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.
Ključne besede: 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
Objavljeno: 10.07.2015; Ogledov: 312; Prenosov: 44
URL Povezava na celotno besedilo

52.
On the remoteness function in median graphs
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Wilfried Imrich, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2009, izvirni znanstveni članek

Opis: Profil grafa ▫$G$▫ je poljubna neprazna multimnožica vozlišč iz ▫$G$▫. Pripadajoča funkcija oddaljenosti priredi vsakemu vozlišču iz ▫$V(G)$▫ vsoto razdalj do vozlišč iz profila. Najprej so dobljene nekatere uporabne lastnosti funkcije oddaljenosti na hiperkockah, nato pa je funkcija oddaljenosti obravnavana na poljubnih medianskih grafih glede na njihove izometrične vložitve v hiperkocke. V posebnem je najdena povezava med vozlišči medianskega grafa ▫$G$▫, katerega funkcija oddaljenosti je največja (antimedianska množica v ▫$G$▫), z antimediansko množico pripadajoče hiperkocke. Medtem ko je za lihe profile antimedianska množica neodvisna množica, ki leži na strogem robu medianskega grafa, obstajajo medianski grafi, v katerih določeni sodi profili porajajo konstantno funkcijo oddaljenosti. Take medianske grafe karakteriziramo na dva načina: kot grafe, katerih periferna transverzala je 2, in kot grafe z geodetskim številom 2. Nazadnje predstavimo algoritem, ki za dani graf ▫$G$▫ z ▫$n$▫ vozlišči in ▫$m$▫ povezavami v času ▫$O(m log n)$▫ odloči, ali je ▫$G$▫ medianski graf z geodetskim številom 2.
Ključne besede: hiperkocka, medianski graf, medianska množica, funkcija oddaljenosti, geodetsko število, periferna transverzala, median graph, median set, remoteness function, geodetic number, periphery transverzal, hypercube
Objavljeno: 10.07.2015; Ogledov: 363; Prenosov: 60
URL Povezava na celotno besedilo

53.
54.
55.
56.
57.
58.
59.
60.
Iskanje izvedeno v 0.25 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici