| Naslov: | CELOŠTEVILSKE DOMINACIJSKE INVARIANTE NA GRAFIH |
|---|
| Avtorji: | ID Komovec, Luka (Avtor)
ID Brešar, Boštjan (Mentor) Več o mentorju...  |
|---|
| Datoteke: |  UNI_Komovec_Luka_2009.pdf (501,60 KB)
MD5: 7E3466DB81BD1165BCD4DA9A9499F507
PID: 20.500.12556/dkum/fe0fef5d-2538-49d9-a751-d3bb9e7253bc
|
|---|
| Jezik: | Slovenski jezik |
|---|
| Vrsta gradiva: | Diplomsko delo |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | 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 |
|---|
| Kraj izida: | Maribor |
|---|
| Založnik: | [L. Komovec] |
|---|
| Leto izida: | 2009 |
|---|
| PID: | 20.500.12556/DKUM-10406 |
|---|
| UDK: | 51(043.2) |
|---|
| COBISS.SI-ID: | 16946440 |
|---|
| NUK URN: | URN:SI:UM:DK:ZWDXKEUX |
|---|
| Datum objave v DKUM: | 17.06.2009 |
|---|
| Število ogledov: | 2734 |
|---|
| Število prenosov: | 214 |
|---|
| 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. |
