| Title: | Nekateri rezultati o povezanosti in neodvisnih množicah v produktih grafov |
|---|
| Authors: | ID Paj Erker, Tjaša (Author)
ID Špacapan, Simon (Mentor) More about this mentor...  |
|---|
| Files: |  DOK_Paj_Erker_Tjasa_2018.pdf (603,74 KB)
MD5: C65739E32C06F33FF33139397AD7277F
PID: 20.500.12556/dkum/e7a4976e-dfb6-4698-82fb-112977d4eca7
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Doctoral dissertation |
|---|
| Typology: | 2.08 - Doctoral Dissertation |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| 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 |
|---|
| Place of publishing: | [Maribor |
|---|
| Publisher: | T. Paj Erker] |
|---|
| Year of publishing: | 2018 |
|---|
| PID: | 20.500.12556/DKUM-70734 |
|---|
| UDC: | 519.171(043.3) |
|---|
| COBISS.SI-ID: | 297733120 |
|---|
| NUK URN: | URN:SI:UM:DK:D9ISO1AH |
|---|
| Publication date in DKUM: | 11.12.2018 |
|---|
| Views: | 1742 |
|---|
| Downloads: | 179 |
|---|
| Metadata: |    |
|---|
| Categories: | FNM
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
