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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 14: Строка 14:
 
3) <tex>\chi(C_{n}) =  
 
3) <tex>\chi(C_{n}) =  
 
   \begin{cases}
 
   \begin{cases}
     2,&TeXt{если n - четное;}\\
+
     2\text{, if $n$ is even;}\\
      3,&TeXt{если n - не четное; }
+
    3\text{, if $n$ is odd.}
 
   \end{cases}
 
   \end{cases}
 
 
 
</tex>
 
</tex>
 +
 +
4) ''G'' - дерево, тогда <tex>\chi(G) = 2</tex>
 +
 +
 +
Задача о нахождении <tex>\chi(G)</tex> является NP-полной.
 +
 +
== Хроматическая функция ==
 +
{{Определение
 +
|definition=<tex>P(G,t)</tex> - число способов раскрасить граф ''G'' в ''t'' цветов.
 +
}}
 +
 +
== Источники ==
 +
1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы.'''ISBN 978-5-8114-1068-2'''<br />
 +
2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Раскраски графов]]

Версия 01:38, 25 октября 2010

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

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

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

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

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

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

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

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

4) G - дерево, тогда [math]\chi(G) = 2[/math]


Задача о нахождении [math]\chi(G)[/math] является NP-полной.

Хроматическая функция

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


Источники

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