хроматично число

Хроматично число (Chromatic number) е най-малката стойност за броя различни цветове необходими за оцветяване върхове на свързан граф, така че два съедни върха да бъдат оцветени различно. Числовата редица е представена в http://oeis.org/A000934 с формулата: a(n) = floor( (7+sqrt(1+48*n))/2 ). Изчисляването на хроматично число често е NP-пълна задача.

Съставете програма, чрез която се въвежда естествено число N от интервала [5..101] и се извеждат посочения брой хроматични числа. Програмата да използва две аналогични функции - рекурсия и итерация.

Допълнителна информация за хроматично число и за оцветяване граф на Petersen само с 3 цвята можете да намерите в: https://en.wikipedia.org/wiki/Graph_coloring, http://mathworld.wolfram.com/ChromaticNumber.html.

Графиката с разпределение на стойностите показва как с нарастване на поредния номер се увеличава и броя последователни равни стойности.

Разгледайте други основни типове примерни задачи, за чието решение се използват числови редици. Потърсете допълнителен материал за: оцветяване върхове на триъгълник.