| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 1 / 1
First pagePrevious page1Next pageLast page
1.
Harmonično barvanje dreves
Luka Žnidarič, 2018, master's thesis

Abstract: Harmonično barvanje grafa je dobro barvanje njegovih vozlišč, tako da se poljuben par različnih barv pojavi na največ enem paru sosednjih vozlišč. Harmonično kromatično število grafa G je najmanjše število barv, ki jih potrebujemo za harmonično barvanje grafa G. Znano je, da je določitev harmoničnega kromatičnega števila grafa NP-težek problem. V magistrskem delu bo pokazano, da problem ostane NP-težek tudi v primeru dreves. Nadalje bodo obravnavane različne družine dreves, za katere je problem lažje rešljiv. Določene bodo natančne vrednosti harmoničnega kromatičnega števila teh dreves, v nekaterih primerih pa bo opisan tudi polinomski algoritem, ki podano drevo harmonično pobarva z želenim številom barv.
Keywords: drevesa, barvanje grafov, harmonično barvanje
Published: 03.10.2018; Views: 187; Downloads: 29
.pdf Full text (822,40 KB)

Search done in 0.02 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica