Coloring, colouring: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''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> …»)
 
Нет описания правки
 
Строка 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.

Текущая версия от 10:46, 24 октября 2018

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.