| Title: | Pakirno barvanje grafa : na študijskem programu 2. stopnje Matematika |
|---|
| Authors: | ID Ličina, Tomaž (Author)
ID Dravec, Tanja (Mentor) More about this mentor...  |
|---|
| Files: |  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
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Master's thesis/paper |
|---|
| Typology: | 2.09 - Master's Thesis |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | barvanje grafov, pakirno barvanje grafov, drevesa, grafi Mycielskega, kartezični produkt grafov, klično število, neodvisnostno število, vozliščno pokritje |
|---|
| Place of publishing: | Maribor |
|---|
| Place of performance: | Maribor |
|---|
| Publisher: | [T. Ličina] |
|---|
| Year of publishing: | 2021 |
|---|
| Number of pages: | 45 str. |
|---|
| PID: | 20.500.12556/DKUM-80891 |
|---|
| UDC: | 519.174(043.2) |
|---|
| COBISS.SI-ID: | 90325763 |
|---|
| Publication date in DKUM: | 12.01.2022 |
|---|
| Views: | 1101 |
|---|
| Downloads: | 82 |
|---|
| 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. |
