Coloring, colouring: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Coloring, colouring''' --- раскраска. '''1.''' Let <math>G</math> be a graph and <math>S</math> be a set of colors. A '''coloring''' of <math>G</math> …») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Coloring, colouring''' | '''Coloring, colouring''' — ''[[раскраска]].'' | ||
'''1.''' Let <math>G</math> be a graph and <math>S</math> be a set of colors. A '''coloring''' of <math>G</math> is | '''1.''' Let <math>\,G</math> be a [[graph, undirected graph, nonoriented graph|graph]] and <math>\,S</math> be a set of colors. A '''coloring''' of <math>\,G</math> is | ||
a mapping <math>f: V(G) \rightarrow S</math> from the vertex set <math>V(G)</math> into <math>S</math> | a mapping <math>\,f: V(G) \rightarrow S</math> from the [[vertex]] set <math>\,V(G)</math> into <math>\,S</math> | ||
such that no two adjacent vertices have the same color, | such that no two adjacent vertices have the same color, | ||
i.e., <math>f(x) \neq f(y)</math> whenever <math>x</math> and <math>y</math> are adjacent. This '''C.''' is called a '''proper''' ('''valid''', | i.e., <math>\,f(x) \neq f(y)</math> whenever <math>\,x</math> and <math>\,y</math> are adjacent. This '''C.''' is called a '''proper''' ('''valid''', | ||
'''legitimate''', '''good''') coloring. | '''legitimate''', '''good''') coloring. | ||
<math>f</math> is called '''<math>k</math>-coloring''' of <math>G</math> if <math>f</math> is a coloring of <math>G</math> into <math>k</math> colors, | <math>\,f</math> is called '''[[k-Coloring|<math>\,k</math>-coloring]]''' of <math>\,G</math> if <math>\,f</math> is a coloring of <math>\,G</math> into <math>\,k</math> colors, | ||
i.e. <math>k=|\{f(p): p\in V(G)\}|</math>. | i.e. <math>\,k=|\{f(p): p\in V(G)\}|</math>. | ||
It is <math>NP</math>-complete to decide if a given graph <math>G</math> admits | It is <math>\,NP</math>-complete to decide if a given graph <math>\,G</math> admits | ||
a <math>k</math>-coloring for a given <math>k</math> except for the cases <math>k</math> = 1 and <math>k</math> = 2. | a <math>\,k</math>-coloring for a given <math>\,k</math> except for the cases <math>\,k</math> = 1 and <math>\,k</math> = 2. | ||
Graph coloring remains <math>NP</math>-complete even on | Graph coloring remains <math>\,NP</math>-complete even on | ||
planar graphs of degree at most 4. | [[planar graph|planar graphs]] of degree at most 4. | ||
'''2.''' | '''2.''' | ||
==See== | ==See== | ||
*''Large-block schema''. | |||
* ''[[Large-block schema]]''. | |||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 12:55, 23 сентября 2014
Coloring, colouring — раскраска.
1. Let [math]\displaystyle{ \,G }[/math] be a graph and [math]\displaystyle{ \,S }[/math] be a set of colors. A coloring of [math]\displaystyle{ \,G }[/math] is a mapping [math]\displaystyle{ \,f: V(G) \rightarrow S }[/math] from the vertex set [math]\displaystyle{ \,V(G) }[/math] into [math]\displaystyle{ \,S }[/math] such that no two adjacent vertices have the same color, i.e., [math]\displaystyle{ \,f(x) \neq f(y) }[/math] whenever [math]\displaystyle{ \,x }[/math] and [math]\displaystyle{ \,y }[/math] are adjacent. This C. is called a proper (valid, legitimate, good) coloring.
[math]\displaystyle{ \,f }[/math] is called [math]\displaystyle{ \,k }[/math]-coloring of [math]\displaystyle{ \,G }[/math] if [math]\displaystyle{ \,f }[/math] is a coloring of [math]\displaystyle{ \,G }[/math] into [math]\displaystyle{ \,k }[/math] colors, i.e. [math]\displaystyle{ \,k=|\{f(p): p\in V(G)\}| }[/math].
It is [math]\displaystyle{ \,NP }[/math]-complete to decide if a given graph [math]\displaystyle{ \,G }[/math] admits a [math]\displaystyle{ \,k }[/math]-coloring for a given [math]\displaystyle{ \,k }[/math] except for the cases [math]\displaystyle{ \,k }[/math] = 1 and [math]\displaystyle{ \,k }[/math] = 2. Graph coloring remains [math]\displaystyle{ \,NP }[/math]-complete even on planar graphs of degree at most 4.
2.
See
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.