| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 1 / 1
First pagePrevious page1Next pageLast page
1.
Nekateri rezultati o povezanosti in neodvisnih množicah v produktih grafov
Tjaša Paj Erker, 2018, doctoral dissertation

Abstract: Doktorska disertacija obravnava nekatere rezultate na grafovskih produktih. V uvodu bomo na kratko predstavili vsebino doktorske disertacije in ponovili nekatere osnovne pojme teorije grafov, ki jih bomo uporabljali v nadaljevanju. Prva tema, ki jo bomo predstavili so neodvisne množice v direktnem produktu. Govorili bomo o velikosti in strukturi največjih neodvisnih množic v direktnem produktu. Najprej bomo predstavili pomembnejše znane rezultate, nato pa bomo pokazali, da ima direkten produkt lihe poti in poljubnega grafa, ter direkten produkt sodega cikla in poljubnega grafa največjo neodvisno množico, ki je unija dveh pravokotnikov. Ugotovili bomo, da obstajajo v direktnem produktu sode poti in poljubnega grafa največje neodvisne množice, ki so lahko tudi drugačne oblike ter zapisali natančno karakterizacijo teh največjih neodvisnih množic. Zapisali bomo zadostni pogoji za drevesa, da ima direkten produkt drevesa in poljubnega grafa največjo neodvisno množico oblike dveh pravokotnikov. V nadaljevanju bomo raziskali posplošeno 3-povezanost v kartezičnem produktu grafov. Prikazali bomo več naravnih načinov, kako dobiti 3-presečno množico S, pri kateri nam graf razpade na vsaj tri komponente. Nato bomo dokazali, da je eden izmed teh načinov vedno optimalen, če sta G in H 2-povezana grafa na vsaj šestih vozliščih. Tako dobimo natančno vrednost posplošene 3-povezanosti kartezičnega produkta dveh 2-povezanih grafov na vsaj šestih vozliščih. Na koncu se bomo ukvarjali z vprašanjem o zgornji meji najmanjšega diametra krepko orientiranega krepkega produkta. Določili bomo natančno vrednost najmanjšega diametra krepkega produkta dveh poti.
Keywords: direktni produkt, kartezični produkt, krepki produkt, neodvisna množica, povezanost, posplošena povezanost, diameter, krepka orientacija
Published: 11.12.2018; Views: 674; Downloads: 73
.pdf Full text (603,74 KB)

Search done in 0.25 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica