| Naslov: | Pakirno barvanje grafa : na študijskem programu 2. stopnje Matematika |
|---|
| Avtorji: | ID Ličina, Tomaž (Avtor)
ID Dravec, Tanja (Mentor) Več o mentorju...  |
|---|
| Datoteke: |  MAG_Licina_Tomaz_2021.pdf (613,60 KB)
MD5: 4AC055439DE1223C1E09402EDCF287F0
PID: 20.500.12556/dkum/af9bc895-96a2-4d29-b5eb-e850cb414fe3
 MAG_Licina_Tomaz_2021.zip (1,76 MB)
MD5: 1D50D94A65E68A27402910AE0C01BCFD
PID: 20.500.12556/dkum/4bb2c28e-1774-49d9-8c59-418f04830db8
|
|---|
| Jezik: | Slovenski jezik |
|---|
| Vrsta gradiva: | Magistrsko delo/naloga |
|---|
| Tipologija: | 2.09 - Magistrsko delo |
|---|
| Organizacija: | FNM - Fakulteta za naravoslovje in matematiko
|
|---|
| Opis: | Pakirno barvanje grafe je dobro barvanje vozlišč, pri katerem sta poljubni dve vozlišči z isto barvo i na razdalji večji kot i. Pakirno kromatično število je najmanjše število barv, ki jih potrebujemo za tako barvanje grafa.
V magistrskem delu obravnavamo pakirno kromatično število nekaterih družin grafov in zvezo pakirnega kromatičnega števila z drugimi grafovskimi invariantami. Podrobneje obravnavamo zvezo med kličnim, kromatičnim in pakirnim kromatičnim številom.
V prvem delu proučujemo pakirno kromatično število na osnovnih družinah grafov, na drevesih, kartezičnih produktih grafov in na grafih Mycielskega. V naslednjem delu obravnavamo grafe z majhnimi pakirnimi kromatičnimi števili in pokažemo, da je preveriti, ali ima graf pakirno kromatično število enako 4, NP-težek problem. V tretjem delu prikažemo zvezo pakirnega kromatičnega števila z neodvisnostnim številom grafa, najmanjšim vozliščnim pokritjem grafa in maksimalno stopnjo v grafu. V zadnjem delu raziskujemo zvezo med kličnim, kromatičnim in pakirnim kromatičnim številom. Poiščemo trojice naravnih števil (a,b,c) za katere obstaja graf G s kličnim številom a, kromatičnim številom b in pakirnim kromatičnim številom c. |
|---|
| Ključne besede: | barvanje grafov, pakirno barvanje grafov, drevesa, grafi Mycielskega, kartezični produkt grafov, klično število, neodvisnostno število, vozliščno pokritje |
|---|
| Kraj izida: | Maribor |
|---|
| Kraj izvedbe: | Maribor |
|---|
| Založnik: | [T. Ličina] |
|---|
| Leto izida: | 2021 |
|---|
| Št. strani: | 45 str. |
|---|
| PID: | 20.500.12556/DKUM-80891 |
|---|
| UDK: | 519.174(043.2) |
|---|
| COBISS.SI-ID: | 90325763 |
|---|
| Datum objave v DKUM: | 12.01.2022 |
|---|
| Število ogledov: | 1102 |
|---|
| Število prenosov: | 82 |
|---|
| 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. |
