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

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


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

Первоначально раскраски графов были нужны для составления географических карт[1]. Сегодня же они (в частности раскраска с использованием минимального количества цветов) используются, например, для составления расписаний, распределения регистров в микропроцессорах, распараллеливания численных методов.[2]

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

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


  • [math]1[/math]-хроматические графы — это нулевые(не имеющие ребер) графы и только они. [math]\chi(O_{n}) = 1[/math].
  • [math]\chi(K_{n}) = n[/math] — хроматическое число полного графа равно [math]n[/math].
  • [math]\chi(C_{n}) = \begin{cases} 2\text{, if $n$ is even;}\\ 3\text{, if $n$ is odd.} \end{cases} [/math]
  • [math]G = (V, E)[/math] — двудольный граф, тогда [math]\chi(G) = 2[/math]


Задача о нахождении [math]\chi(G)[/math] не разрешима за полиномиальное время.

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

Основная статья: Хроматический многочлен
Определение:
Хроматический многочлен (англ. Chromatic polynomial) [math]P(G, t)[/math] — число способов раскрасить граф [math]G[/math] в [math]t[/math] цветов.

Примечания

Источники информации

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