Narodna in univerzitetna knjižnica, Ljubljana (NUK)
-
Structural approach to the crossing number of graphs : doctoral thesisBokal, Drago, 1978-Raziskovanje prekrižno-kritičnih grafov je začel Širáň, ki je za vsak cel ▫$k \ge 3$▫ konstruiral neskončno družino ▫$3$▫-povezanih ▫$k$▫-prekrižno-kritičnih grafov. Kochol je za vsak cel ▫$k \ge 2$▫ ... konstruiral neskončno družino enostavnih ▫$3$▫-povezanih ▫$k$▫-prekrižno-kritičnih grafov. Richter in Thomassen sta začela s študijem stopenj vozlišč v prekrižno-kritičnih grafih, ko sta pokazala, da za vsaka cela ▫$r \ge 6$▫ in ▫$k \ge 1$▫ obstaja le končno mnogo ▫$k$▫-prekrižno-kritičnih grafov z minimalno stopnjo ▫$r$▫. Salazar je opazil, da iz njunega argumenta sledi obstoj le končno mnogo ▫$k$▫-prekrižno-kritičnih grafov s povprečno stopnjo ▫$r$▫ za vsak cel ▫$k \ge 1$▫ in vsak racionalen ▫$r>6$▫. Pokazal je, da za vsak racionalen ▫$r \in (4,6)$▫ obstaja tako zaporedje ▫$\{k_{r,i}\}_{i=0}^{\infty}$▫, da za vsak ▫$i \in \NN$▫ obstaja neskončna družina ▫$k_{r,i}$▫-prekrižno-kritičnih grafov s povprečno stopnjo ▫$r$▫, in vprašal po obstoju takih družin za ▫$r \in (3,4)$▫. Na vprašanje sta delno pozitivno odgovorila Pinontoan in Richter,ki sta razvila teorijo tlakovcev in z njeno pomočjo konstruirala iskane družine za $r \in (3\frac{1}{2},4)$▫. V disertaciji nadgradimo njuno delo,da omogoči posplošitev prekrižno-kritičnih grafov, ki jih je konstruiral Kochol. Kombinacija teorije tlakovcev in nove operacije na grafih in njihovih risbah, šiva, nam omogoči popoln odgovor na Salazarjevo vprašanjein njegovo povezavo z rezultati Širáňa in Kochola v obliki naslednjega izreka: obstaja taka zvezna konveksna funkcija $f:(3,6) \to \RR^+$▫, da za vsako racionalno število ▫$r \in (3,6)$▫ in vsako celo število ▫$k \ge f(r)$▫ obstaja neskončna družina prekrižno-kritičnih grafov s povprečno stopnjo ▫$r$▫ in prekrižnim številom ▫$k$▫. Beineke in Ringeisen sta raziskovala prekrižno število kartezičnih produktov malih grafov in ciklov ter določila natančne vrednosti za vse ▫$C_n \Box G$▫, kjer je ▫$G$▫ poljuben graf reda štiri, razen ▫$3$▫-zvezda ▫$K_{1,3}$▫. Jendrol' in Ščerbová sta zapolnila to vrzel. Ugotovila sta tudi prekrižno število ▫$P_m \Box K_{1,3}$▫ in postavila domnevo za splošen rezultat o $P_m \Box K_{1,n}$▫. Domnevo je za ▫$n = 4$▫ dokazal Klešč. V nekoliko splošnejši različici jo za vsak ▫$n \ge 3$▫ dokažemo v pričujočem delu: rezultat Asana o prekrižnem številu grafa ▫$K_{1,3,n}$▫ povežemo z operacijo šiv in dobimo prekrižno število grafa $T \Box K_{1,n}$▫, kjer je ▫$T$▫ poljubno drevo z maksimalno stopnjo tri in ▫$n \ge 3$▫ poljubno celo število. Ta rezultat dopolnimo s prekrižnim številom grafov ▫$T \Box K_{1,3}$▫ za poljubno drevo ▫$T$▫, prekrižnim številom grafov ▫$P_m \Box W_n$▫ za poljubna ▫$m \ge 1$▫, ▫$n \ge 3$▫, ter več drugimi eksaktnimi rezultati in mejami. Seymour je obžaloval, da prekrižno število ne sodeluje na naraven način s teorijo grafovskih minorjev: stiskanje povezave lahko vrednost te invariante poveča ali zmanjša. V tem delu uvedemo minorsko prekrižno število. To je minorsko monotona invarianta, ki omogoča dodatno zmanjševanje števila križišč v risbi, tako da vozlišča zamenjamo z z drevesi in minimiziramo število križišč v risbah vseh takih grafov. Ta invarianta ima bolj naravne uporabe pri izdelavi elektronskih vezij kot navadno prekrižno število. V delu pokažemo več splošnih mej za njeno vrednost, raziščemo strukturo grafov z omejenim minorskim prekrižnim številom in predstavimo nekaj eksaktnih rezultatov in mej za posamezne družine grafov. Ena od spodnjih mej je posplošitev rezultata Morene in Salazarja, ki sta prekrižno število grafa omejila s prekrižnim številom njegovega minorja z majhno maksimalno stopnjo.Vrsta gradiva - disertacija ; neleposlovje za odrasleZaložništvo in izdelava - Ljubljana : [D. Bokal], 2006Jezik - angleškiCOBISS.SI-ID - 14039129
Avtor
Bokal, Drago, 1978-
Drugi avtorji
Mohar, Bojan, 1956-
Teme
Grafi |
Disertacije |
teorija grafov |
prekrižno število |
prekrižno-kritičen graf |
povprečna stopnja |
kartezični produkt |
zvezda |
pot |
drevo |
kolo |
minorsko prekrižno število |
grafovski minor
Rezervirajte gradivo na želenem mestu prevzema.
Mesto prevzema |
Status gradiva | Rezervacija |
---|---|---|
Časopisna čitalnica |
prosto - za čitalnico
|
|
Velika čitalnica |
prosto - za čitalnico
|
Signatura – lokacija, inventarna št. ... |
Status izvoda |
---|---|
GS II 0000619589 glavno skladišče GS II 619589 glavno skladišče |
prosto - za čitalnico
|
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 |
---|---|
Bokal, Drago, 1978- | 22402 |
Mohar, Bojan, 1956- | 01931 |
Vir: Osebne bibliografije
in: SICRIS
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Naslov za dostavo:
Med podatki člana manjka naslov.
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.
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Gradivo iz matične enote je brezplačno. Če je gradivo na mesto prevzema dostavljeno iz drugih enot, lahko knjižnica to storitev zaračuna.
Mesto prevzema | Status gradiva | Rezervacija |
---|
Rezervacija v teku
Prosimo, počakajte trenutek.
Rezervacija je uspela.
Rezervacija ni uspela.
Rezervacija...
Članska izkaznica:
Mesto prevzema:
Naročanje gradiva za izposojo v čitalnice
Naročanje kopij člankov
Urnik dostave gradiva z oznako DS v signaturi