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.
Type of material - dissertation
; adult, serious
Publication and manufacture - Miklavž : [I. Peterin], 2005
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
