Multi-coloring

Материал из WEGA
Перейти к навигации Перейти к поиску

Multi-coloring --- мультираскраска.

For a weighted undirected simple graph [math]\displaystyle{ G = (V,E) }[/math] with [math]\displaystyle{ n }[/math] vertices, let the length of a vertex [math]\displaystyle{ v }[/math] be a positive integer denoted by [math]\displaystyle{ x(v) }[/math] and called the color requirement of [math]\displaystyle{ v }[/math]. A multi-coloring of the vertices of [math]\displaystyle{ G }[/math] is a mapping into the power set of the positive integers, [math]\displaystyle{ \Psi: \; V \rightarrow 2^{N} }[/math], such that [math]\displaystyle{ |\Psi(v)| = x(v) }[/math] and adjacent vertices receive non-intersecting sets of colors. The traditional optimization goal is to minimize the total numbers of colors assigned to [math]\displaystyle{ G }[/math].