| Title: | Hevristični algoritem za 3-barvanje grafov |
|---|
| Authors: | ID Arnečič, Luka (Author)
ID Taranenko, Andrej (Mentor) More about this mentor...  |
|---|
| Files: |  MAG_Arnecic_Luka_2015.pdf (860,06 KB)
MD5: 4039D7A3156B7D93AF23B4B4CED75FF3
|
|---|
| Language: | Slovenian |
|---|
| Work type: | Master's thesis/paper (mb22) |
|---|
| Typology: | 2.09 - Master's Thesis |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | Magistrsko delo obravnava hevristični algoritem za 3-barvanje grafov, ki temelji na hibridiziranem evolucijskem algoritmu in se lahko uporabi za ugotavljanje dobre 3-obarvljivosti navadnih neusmerjenih grafov. Najprej razložimo matematične osnove problema in predstavimo algoritme, na katerih temelji naš hevristični algoritem, nato ga opišemo, na koncu pa predstavimo primerjavo hevrističnega algoritma z algoritmi uporabljenimi in opisanimi v osnovnem članku [9].
V prvem delu razložimo matematične osnove, ki so potrebne za razumevanje problema dobrega 3-barvanja grafov in predstavimo osnovne zasnove algoritmov, na katerih temelji hevristični algoritem.
V drugem delu predstavimo hevristični algoritem po komponentah ter podatkovne strukture, ki so uporabljene v hevrističnem algoritmu. Vsako komponento algoritma natančno opišemo in predstavimo idejo, za katero je bila uporabljena.
V tretjem delu predstavimo primerjavo hevrističnega algoritma z algoritmi, uporabljenimi in opisanimi v osnovnem članku [9]. |
|---|
| Keywords: | barvanje grafov, algoritmi na grafih, diskretni algoritmi, hevristike |
|---|
| Year of publishing: | 2015 |
|---|
| Publisher: | [L. Arnečič] |
|---|
| Source: | Maribor |
|---|
| PID: | 20.500.12556/DKUM-55549 |
|---|
| UDC: | 004.421.2:519.174.7(043.2) |
|---|
| COBISS.SI-ID: | 21895944 |
|---|
| NUK URN: | URN:SI:UM:DK:RX5I2VLV |
|---|
| Publication date in DKUM: | 15.02.2016 |
|---|
| Views: | 1530 |
|---|
| Downloads: | 156 |
|---|
| Metadata: |     |
|---|
| Categories: | FNM
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | 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. |
