Nekatere faktorizacije v metrični teoriji grafov : doktorska disertacija
Peterin, Iztok
Delo začenjamo z definicijami in nekaj dobro znanimi rezultati o kartezičnem produktu, Djoković-Winkler-jevi relaciji ▫$\Theta$▫, delnih kockah, medianskih in ravninskih grafih. V nadaljevanju ...predstavimo topološko lastnost ličnost, ki nam pomaga pri karakterizaciji ravninskih medianskih grafov. Bolj natančno, graf ▫$G$▫ je ravninski medianski graf natanko tedaj, ko ga lahko dobimo iz ▫$K_1$▫ z zaporedjem perifernih konveksnih ličnih ekspanzij, pri čemer lična pomeni, da so vse ekspandirane točke na nekem koraku ekspanzije na istem licu. Nadalje obravnavamo skoraj-medianske grafe, kjer predstavimo dve njihovi ravninski družini. Ena je posplošitev benzenoidnih grafov, druga pa dvodelnih koles. Predstavljen je algoritem, ki v ▫$O(m\log n)$▫ času prepozna ali je graf ▫$G$▫ skoraj-medianski z dodatno lastnostjo, da so vsi ▫$\langle U_{ab}\rangle$▫-ji zunanje ravninski grafi. Med njimi so tudi vsi ravninski skoraj-medianski grafi. Zajeten del tega dela predstavljajo karakterizacije raznih podgrafov kartezičnih produktov. Tako s pomočjo faktorizacij, ki so predstavljene z označitvami povezav, natanko pokažemo, katere grafe lahko vložimo v kartezični produkt kvocientnih grafov porojenih s prej omenjeno označitvijo povezav. Predstavimo karakterizacije podgrafov in induciranih podgrafov kartezičnih produktov, kot tudi karakterizacije podgrafov, induciranih podgrafov in izometričnih podgrafov Hammingovih grafov. Pri vseh je uporabljena podobna metoda, ki je sestavljena iz pogojev za označevanje povezav, ki morajo biti izpolnjeni. Tako je na primer graf ▫$G$▫ induciran podgraf Hammingovega grafa natanko tedaj, ko imajo povezave, ki pripadajo istemu trikotniku, enako oznako in za dve različni nesosednji točki ▫$u$▫ in ▫$v$▫ morata obstajati dve različni oznaki ▫$i$▫ in ▫$j$▫ na vsaki inducirani ▫$u,v$▫-poti. S podobno metodo so predstavljeni tudi zastavni grafi. To so grafi, ki imajo za množico točk zastave stopničasto delno urejene množice. Dve zastavi sta sosedi, če se razlikujeta v natanko enem elementu. Na koncu predstavimo linearni algoritem za prafaktorizacijo kartezičnega produkta. Le-ta je hitrejši in konceptualno enostavnejši od prejšnjih algoritmov za ta problem.
Vrsta gradiva - disertacija
; neleposlovje za odrasle
Založništvo in izdelava - Miklavž : [I. Peterin], 2005
GS II 0000607875 glavno skladišče
GS II 607875 glavno skladišče
prosto - za čitalnico
Vnos na polico
Dodajanje gradiva na polico je uspelo.
Dodajanje gradiva na polico je spodletelo.
Dodajanje gradiva na polico ni bilo potrebno.
Bibliografsko gradivo je bilo uspešno dodano na polico.
Dodajanje bibliografskega gradiva na polico ni uspelo.
Gradivo je že na polici.
Trajna povezava
URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto
Faktor vpliva
Izdaja
Kategorija
Razvrstitev
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Izberite knjižnično izkaznico:
Baze podatkov,
v katerih je revija indeksirana
Ime baze podatkov
Področje
Leto
Povezave do osebnih bibliografij avtorjev
Povezave do podatkov o raziskovalcih v sistemu SICRIS
Storitev za pridobivanje naslova trenutno ni dostopna, prosimo, poskusite še enkrat.
S klikom na gumb "V redu" boste potrdili zgoraj izbrano prevzemno mesto in dokončali postopek rezervacije.
S klikom na gumb "V redu" boste potrdili zgoraj izbrano prevzemno mesto in naslov za dostavo ter dokončali postopek rezervacije.
S klikom na gumb "V redu" boste potrdili zgoraj izbrani naslov za dostavo in dokončali postopek rezervacije.
Obvestilo
Trenutno je storitev za avtomatsko prijavo in rezervacijo nedostopna. Gradivo lahko rezervirate sami na portalu Biblos ali ponovno poskusite tukaj kasneje.
Citiranje
Funkcionalnost trenutno ni na voljo. Prosimo, poskusite kasneje.
Naročanje gradiva za izposojo v čitalnice
Naročanje kopij člankov
Urnik dostave gradiva z oznako DS v signaturi