Раскраска графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition= Раскраской графа <tex>G(V,E)</tex> называется такое отображение <tex>\phi</tex> из …»)
(нет различий)

Версия 00:27, 25 октября 2010

Определение:
Раскраской графа [math]G(V,E)[/math] называется такое отображение [math]\phi[/math] из множества вершин V в множество красок { [math]c_1...c_t[/math] } что для любых двух смежных вершин u и v выполняется [math]\phi(u)\ne\phi(v)[/math]. Так же её называют t-раскраской.


Хроматическое число

Определение:
Хроматическим числом [math]\chi(G)[/math] графа [math]G(V,E)[/math] называется такое минимальное число t, для которого существует t-раскраска графа.