20.500.12556/DKUM-72167 Harmonično barvanje dreves Harmonious colouring of trees 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. Harmonious colouring of a graph is a proper vertex colouring such that every pair of colours appears on at most one pair of adjacent vertices. The harmonious chromatic number is the minimum number of colours needed for such a colouring. In this master thesis we deal with the problem of finding a harmonious colouring for trees. We research this problem on trees in general and later on trees of specific types. In the first part we focus on the problem in the case of trees in general. We show that the problem of finding the harmonious chromatic number of a tree is NP-hard. In the second part we limit ourselves to the trees of specific types. For trees with these limitations we present better bounds for their harmonious chromatic number. We also present a polynomial algorithm for finding a harmonious colouring for some of those trees. drevesa barvanje grafov harmonično barvanje trees graph colouring harmonious colouring true true false [L. Žnidarič] Slovenski jezik Angleški jezik Magistrsko delo/naloga 2018-09-12 22:49:33 2018-10-03 15:50:19 2022-08-01 22:03:16 2019-07-11 19:05:34 2018 0 Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.172:519.174.7(043.2) 24054536 URN:SI:UM:DK:GOM63VKE MAG_Znidaric_Luka_2018.pdf MAG_Znidaric_Luka_2018.pdf 1 680315470993C8CD0FF051647DF74D26 56b8edaeaff595954730d3521347e45908f3932ca1032bcd48b8ced3ba6b6a7b 4f668f79-7c10-11eb-bb7a-00155d0001ca 20.500.12556/dkum/3dd73ee5-2a21-45dc-8d71-a49e02f2c4b4 https://dk.um.si/Dokument.php?lang=slv&id=129327 Fakulteta za naravoslovje in matematiko 0 0 0