| Title: | CELOŠTEVILSKE DOMINACIJSKE INVARIANTE NA GRAFIH |
|---|
| Authors: | ID Komovec, Luka (Author)
ID Brešar, Boštjan (Mentor) More about this mentor...  |
|---|
| Files: |  UNI_Komovec_Luka_2009.pdf (501,60 KB)
MD5: 7E3466DB81BD1165BCD4DA9A9499F507
PID: 20.500.12556/dkum/fe0fef5d-2538-49d9-a751-d3bb9e7253bc
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Undergraduate thesis |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | Naj bo Y podmnožica množice celih števil in G = (V,,E) graf. Funkcija, ki vsakemu vozlišču priredi neko vrednost iz množice Y, tako da je seštevek vrednosti v soseščini vsakega vozlišča vsaj 1, se imenuje celoštevilska dominacijska funkcija grafa G. Vrednost celoštevilske dominacijske funkcije v poljubni podmnožici S množice V definiramo kot seštevek vrednosti v vsakem vozlišču iz S. Teža celoštevilske dominacijske funkcije je vrednost funkcije v množici vozlišč V. Poiskati želimo po teži najmanjšo celoštevilsko dominacijsko funkcijo grafa G.
V tem delu so predstavljene variacije različnih celoštevilskih dominacij, kot so {k}-dominacija, k-kratna dominacija, predznačena dominacija in minus dominacija, ki jih obravnavamo na razredih grafov kot so poti, cikli, pahljače, kolesa, ponve in trampolini. Podan je algoritem, ki v linearnem času reši problem L-dominacije na strogo tetivnih grafih. Prav tako je podana časovna zahtevnost izračuna naštetih celoštevilskih dominacijskih invariant za razrede dualno tetivnih, dvojno tetivnih in ravninskih grafov. Na koncu je na podoben način predstavljena 2-mavrična dominacija. |
|---|
| Keywords: | celoštevilska dominacija, k-kratna dominacija, predznačena dominacija, minus dominacija, {k}-dominacija, 2-mavrična dominacija, tetivni grafi, dualno tetivni grafi, dvojno tetivni grafi, strogo tetivni grafi |
|---|
| Place of publishing: | Maribor |
|---|
| Publisher: | [L. Komovec] |
|---|
| Year of publishing: | 2009 |
|---|
| PID: | 20.500.12556/DKUM-10406 |
|---|
| UDC: | 51(043.2) |
|---|
| COBISS.SI-ID: | 16946440 |
|---|
| NUK URN: | URN:SI:UM:DK:ZWDXKEUX |
|---|
| Publication date in DKUM: | 17.06.2009 |
|---|
| Views: | 2733 |
|---|
| Downloads: | 214 |
|---|
| 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. |
