-
Nekatere faktorizacije v metrični teoriji grafov : doktorska disertacijaPeterin, IztokDelo 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 odrasleZaložništvo in izdelava - Miklavž : [I. Peterin], 2005Jezik - slovenskiCOBISS.SI-ID - 14096648
Avtor
Peterin, Iztok
Drugi avtorji
Klavžar, Sandi |
Imrich, Wilfried
Teme
Grafi |
Disertacije |
teorija grafov |
Disertacije |
matematika |
kombinatorika |
teorija grafov |
kartezični produkt grafov |
faktorizacija |
Hammingovi grafi |
podgrafi |
inducirani podgrafi |
zastavni grafi |
ravninski medianski grafi |
skoraj-medianski grafi |
disertacije |
mathematics |
combinatorics |
graph theory |
Cartesian product graphs |
factorization |
Hamming graphs |
subgraphs |
induced subgraphs |
flag graphs |
planar median graphs |
almost-median graphs
Knjižnica/institucija |
Kraj | Akronim | Za izposojo | Druga zaloga |
---|---|---|---|---|
FMF in IMFM, Matematična knjižnica, Ljubljana | Ljubljana | MAKLJ |
v čitalnico 1 izv.
|
|
Miklošičeva knjižnica - FPNM, Maribor | Maribor | PEFMB |
v čitalnico 1 izv.
|
|
Narodna in univerzitetna knjižnica, Ljubljana | Ljubljana | NUK |
v čitalnico 1 izv.
|
|
Univerzitetna knjižnica Maribor | Maribor | UKM |
v čitalnico 1 izv.
|
Vnos na polico
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 |
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 |
---|---|
Peterin, Iztok | 20839 |
Klavžar, Sandi | 05949 |
Imrich, Wilfried | 11754 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.