Раскраска графа

Раскраска графа

Определение:

Правильной раскраской графа [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-раскраской.

Раскраской графа чаще всего называют именно правильную раскраску. Так же её называют t-раскраской.

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

Определение:

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

Хроматические числа различных графов

1) 1-хроматические графы - это нулевые графы и только они. [math]\chi(O_{n}) = 1[/math].

2) [math]\chi(K_{n}) = n[/math] - хроматическое число полного графа равно n.

3) [math]\chi(C_{n}) = \begin{cases} 2\text{, if $n$ is even;}\\ 3\text{, if $n$ is odd.} \end{cases} [/math]

4) G - дерево, тогда [math]\chi(G) = 2[/math]

Задача о нахождении [math]\chi(G)[/math] является NP-полной.

Хроматическая функция

Определение:

[math]P(G,t)[/math] - число способов раскрасить граф G в t цветов.

Источники

1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
2. Харари Ф. - Теория графов. ISBN 978-5-397-00622-4