| Naslov: | Algebra poti in dominantni problemi na grafovskih produktih |
|---|
| Avtorji: | ID Pavlič, Polona (Avtor)
ID Žerovnik, Janez (Mentor) Več o mentorju...  |
|---|
| Datoteke: |  DR_Pavlic_Polona_2013.pdf (1,51 MB)
MD5: 3A85A43525F5A485C3548E8B91E76E68
PID: 20.500.12556/dkum/1ee39f50-628d-493f-8777-d17b6ec3cb9e
|
|---|
| Jezik: | Slovenski jezik |
|---|
| Vrsta gradiva: | Doktorska disertacija |
|---|
| Tipologija: | 2.08 - Doktorska disertacija |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | Različni problemi grafovskih invariant predstavljajo velik del študij na področju teorije grafov. Ker so ti problemi v veliki meri NP-polni, je smiselno iskati rešitve na določenih zanimivih družinah grafov. V tem delu se omejimo na probleme dominacije na družini poligrafov. To so grafi, ki izhajajo iz kemijske teorije grafov in so matematični model kemijske strukture polimera. V kemiji je polimer makromolekula, ki ima posebno ponavljajočo se strukturo molekul, povezanih s kovalentnimi vezmi. Mi se posebej omejimo na primere, ko so te ponavljajoče enote enake, oziroma v jeziku teorije grafov, ko so monografi izomorfni, ter so povezave med njimi enake. Taki grafi se imenujejo rotagrafi, če pa med prvim in zadnjim monografom ni povezav, imenujemo tak poligraf fasciagraf.
S pomočjo algebre poti pokažemo, da se različni problemi dominacije na razredu poligrafov za fiksno velikost monografa lahko rešijo v konstantnem času. Ker so posebni primeri poligrafov tudi grafovski produkti poti in ciklov, za kartezični in direktni produkt implementiramo algoritem in dobimo formule za dominantna, neodvisna dominantna ter rimska dominantna števila teh grafov, kjer je eden od faktorjev fiksen. Nadalje pokažemo, da se preučevane grafovske invariante na fasciagrafih in rotagrafih, pri katerih je monograf enak, lahko razlikujejo le za konstantno vrednost, natančneje, za končno število (različnih) konstant. Nazadnje še rešimo problem rimskega dominantnega števila na leksikografskem produktu grafov. Z vpeljavo koncepta tako imenovanih dominatnih parov za poljubna grafa podamo formulo, ki določi rimsko dominantno število njunega leksikografskega produkta. Podamo tudi nove neskončne družine rimskih grafov. |
|---|
| Ključne besede: | grafovski produkt, dominacija, algebra poti, konstantni algoritem, mreža, torus |
|---|
| Kraj izida: | [Maribor |
|---|
| Založnik: | P. Pavlič] |
|---|
| Leto izida: | 2013 |
|---|
| PID: | 20.500.12556/DKUM-40005 |
|---|
| UDK: | 519.17(043.3) |
|---|
| COBISS.SI-ID: | 19789064 |
|---|
| NUK URN: | URN:SI:UM:DK:G9UIGGV9 |
|---|
| Datum objave v DKUM: | 04.04.2013 |
|---|
| Število ogledov: | 2954 |
|---|
| Število prenosov: | 248 |
|---|
| Metapodatki: |    |
|---|
| Področja: | FNM
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
