<?xml version="1.0"?>
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:dc="http://purl.org/dc/elements/1.1/"><rdf:Description rdf:about="https://dk.um.si/IzpisGradiva.php?id=72167"><dc:title>Harmonično barvanje dreves</dc:title><dc:creator>Žnidarič,	Luka	(Avtor)
	</dc:creator><dc:creator>Jakovac,	Marko	(Mentor)
	</dc:creator><dc:subject>drevesa</dc:subject><dc:subject>barvanje grafov</dc:subject><dc:subject>harmonično barvanje</dc:subject><dc:description>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.</dc:description><dc:publisher>[L. Žnidarič]</dc:publisher><dc:date>2018</dc:date><dc:date>2018-09-12 22:49:33</dc:date><dc:type>Magistrsko delo/naloga</dc:type><dc:identifier>72167</dc:identifier><dc:language>sl</dc:language></rdf:Description></rdf:RDF>