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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
|definition= '''Правильной раскраской''' (англ. ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\varphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1...c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\varphi(u)\ne\varphi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.
+
|definition= '''Правильной раскраской''' (англ. ''Regular coloring'') графа <tex>G(V,E)</tex> называется такое отображение <tex>\varphi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1 \ldots c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\varphi(u)\ne\varphi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.
 
}}
 
}}
 
[[Файл:Paint.png|200px|thumb|center|Пример раскраски графа из четырех вершин.]]
 
[[Файл:Paint.png|200px|thumb|center|Пример раскраски графа из четырех вершин.]]
Строка 34: Строка 34:
 
{{main|Хроматический многочлен}}
 
{{main|Хроматический многочлен}}
 
{{Определение
 
{{Определение
|definition=Хроматический многочлен (англ. ''Chromatic polynomial'') <tex>P(G, t)</tex> {{---}} число способов раскрасить граф <tex>G</tex> в <tex>t</tex> цветов.
+
|definition='''Хроматический многочлен''' (англ. ''Chromatic polynomial'') <tex>P(G, t)</tex> {{---}} число способов раскрасить граф <tex>G</tex> в <tex>t</tex> цветов.
 
}}
 
}}
 +
 +
==Связь хроматического числа и хроматического многочлена==
 +
*Минимальное натуральное число, на котором хроматический многочлен для данного графа принимает натуральное значение, является хроматическим числом для данного графа. Поэтому если известен хроматический многочлен, то хроматическое число можно определить последовательной подстановкой. Однако задача о нахождении хроматического многочлена также не разрешима за полиномиальное время.
 +
*В обратную сторону, т.е. если известно хроматическое число, построить хроматический многочлен не получится. Так как оно не дает почти никакой информации о структуре графа.
 +
 
==Примечания==
 
==Примечания==
 
<references/>
 
<references/>
  
 
==Источники информации==
 
==Источники информации==
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
+
* Асанов М. О., Баранский В. А., Расин В. В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
+
* Харари Ф. {{---}} Теория графов. '''ISBN 978-5-397-00622-4'''
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Раскраски графов]]
 
[[Категория: Раскраски графов]]

Текущая версия на 16:47, 8 ноября 2015

Определение:
Правильной раскраской (англ. Regular coloring) графа [math]G(V,E)[/math] называется такое отображение [math]\varphi[/math] из множества вершин [math]V[/math] в множество красок [math]\{c_1 \ldots 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] цветов.


Связь хроматического числа и хроматического многочлена[править]

  • Минимальное натуральное число, на котором хроматический многочлен для данного графа принимает натуральное значение, является хроматическим числом для данного графа. Поэтому если известен хроматический многочлен, то хроматическое число можно определить последовательной подстановкой. Однако задача о нахождении хроматического многочлена также не разрешима за полиномиальное время.
  • В обратную сторону, т.е. если известно хроматическое число, построить хроматический многочлен не получится. Так как оно не дает почти никакой информации о структуре графа.

Примечания[править]

Источники информации[править]

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