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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Хроматическое число)
Строка 1: Строка 1:
== Раскраска графа ==
 
 
 
{{Определение
 
{{Определение
|definition= '''Правильной раскраской графа''' <tex>G(V,E)</tex> называется такое отображение <tex>\phi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1...c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\phi(u)\ne\phi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.
+
|definition= '''Правильной раскраской''' (англ. regular coloring) графа <tex>G(V,E)</tex> называется такое отображение <tex>\phi</tex> из множества вершин <tex>V</tex> в множество красок <tex>\{c_1...c_t\}</tex>, что для любых двух смежных вершин <tex>u</tex> и <tex>v</tex> выполняется <tex>\phi(u)\ne\phi(v)</tex>. Так же её называют '''<tex>t</tex>-раскраской'''.
 
}}
 
}}
 
[[Файл:Paint.png|200px|thumb|center|Пример раскраски графа из четырех вершин.]]
 
[[Файл:Paint.png|200px|thumb|center|Пример раскраски графа из четырех вершин.]]
Строка 8: Строка 6:
  
 
Раскраской графа чаще всего называют именно правильную раскраску.
 
Раскраской графа чаще всего называют именно правильную раскраску.
<br clear = "all">
+
 
 +
Первоначально раскраски графов были нужны для составления географических карт<ref name="4problem"> [http://ru.wikipedia.org/wiki/Проблема_четырёх_красок Проблема четырёх красок]</ref>. Сегодня же они (в частности раскраска с использованием минимального количества цветов) используются, например, для составления расписаний, распределения регистров в микропроцессорах, распараллеливания численных методов.<ref name="pract">[http://ru.wikipedia.org/wiki/Практическое_применение_раскраски_графов Практическое применение раскраски графов]</ref>
  
 
== Хроматическое число ==
 
== Хроматическое число ==
 
{{Определение
 
{{Определение
 
|id= chromatic_number_difinition  
 
|id= chromatic_number_difinition  
|definition= '''Хроматическим числом''' <tex>\chi(G)</tex> графа <tex>G(V,E)</tex> называется такое минимальное число <tex>t</tex>, для которого существует <tex>t</tex>-раскраска графа.
+
|definition= '''Хроматическим числом''' (англ. chromatic number) <tex>\chi(G)</tex> графа <tex>G(V,E)</tex> называется такое минимальное число <tex>t</tex>, для которого существует <tex>t</tex>-раскраска графа.
 
}}
 
}}
  
Строка 36: Строка 35:
 
{{main|Хроматический многочлен}}
 
{{main|Хроматический многочлен}}
 
{{Определение
 
{{Определение
|definition=Хроматическим многочлен <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> цветов.
 
}}
 
}}
  
Строка 42: Строка 41:
 
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
 
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />
 
2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
 
2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
 +
== Примечания ==
 +
<references/>
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Раскраски графов]]
 
[[Категория: Раскраски графов]]

Версия 14:55, 6 января 2014

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


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

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

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

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


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

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

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

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

4) [math]G[/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

Примечания