1632
правки
Изменения
м
== Хроматические числа различных графов ==1) * <tex>1</tex>-хроматические графы {{- --}} это нулевые (не имеющие ребер) графы и только они. <tex>\chi(O_{n}) = 1</tex>.
2) * <tex>\chi(K_{n}) = n</tex> {{---}} хроматическое число полного графа равно <tex>n</tex>.
3) * <tex>\chi(C_{n}) =
4) * <tex>G= (V, E)</tex> {{--- дерево}} двудольный граф, тогда <tex>\chi(G) = 2</tex>
rollbackEdits.php mass rollback
{{Определение
|definition= '''Правильной раскраской''' (англ. regular ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\phivarphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1...\ldots 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> цветов.
}}
== Источники Связь хроматического числа и хроматического многочлена==1*Минимальное натуральное число, на котором хроматический многочлен для данного графа принимает натуральное значение, является хроматическим числом для данного графа. Асанов МПоэтому если известен хроматический многочлен, то хроматическое число можно определить последовательной подстановкой. ООднако задача о нахождении хроматического многочлена также не разрешима за полиномиальное время.*В обратную сторону, Баранский Вт. Ае.если известно хроматическое число, Расин В. Впостроить хроматический многочлен не получится. - Дискретная математика: Графы, матроиды, алгоритмыТак как оно не дает почти никакой информации о структуре графа. '''ISBN 978-5-8114-1068-2'''<br />2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''== Примечания ==
<references/>
==Источники информации==
* Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
* Харари Ф. {{---}} Теория графов. '''ISBN 978-5-397-00622-4'''
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]
