68
правок
Изменения
Нет описания правки
{{Определение
|definition= '''Правильной раскраской''' (англ. regular ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\phivarphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1...c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\phivarphi(u)\ne\phivarphi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.
}}
[[Файл:Paint.png|200px|thumb|center|Пример раскраски графа из четырех вершин.]]
Первоначально раскраски графов были нужны для составления географических карт<ref name="4problem"> [http://ru.wikipedia.org/wiki/Проблема_четырёх_красок Проблема четырёх красок]</ref>. Сегодня же они (в частности раскраска с использованием минимального количества цветов) используются, например, для составления расписаний, распределения регистров в микропроцессорах, распараллеливания численных методов.<ref name="pract">[http://ru.wikipedia.org/wiki/Практическое_применение_раскраски_графов Практическое применение раскраски графов]</ref>
== Хроматическое число Хроматические числа различных графов==
{{Определение
|id= chromatic_number_difinition
|definition= '''Хроматическим числом''' (англ. chromatic ''Chromatic number'') <tex>\chi(G)</tex> графа <tex>G(V,E)</tex> называется такое минимальное число <tex>t</tex>, для которого существует <tex>t</tex>-раскраска графа.
}}
\begin{cases}
2\text{, if $n$ is even;}\\
</tex>
Задача о нахождении <tex>\chi(G)</tex> [[NP-полнота_задачи_о_раскраске_графа | не разрешима за полиномиальное время]].
== Хроматический многочлен ==
{{main|Хроматический многочлен}}
{{Определение
|definition=Хроматический многочлен (англ. chromatic ''Chromatic polynomial'') <tex>P(G, t)</tex> {{---}} число способов раскрасить граф <tex>G</tex> в <tex>t</tex> цветов.
}}
==Примечания==
<references/>
== Источники информации==
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]
