Harmonično barvanje drevesŽnidarič, Luka (Avtor) Jakovac, Marko (Mentor) drevesabarvanje grafovharmonično barvanjeHarmonič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.[L. Žnidarič]20182018-09-12 22:49:33Magistrsko delo/naloga72167UDK: 519.172:519.174.7(043.2)COBISS_ID: 24054536NUK URN: URN:SI:UM:DK:GOM63VKEsl