K-Colored graph: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''<math>k</math>-Colored graph''' --- <math>k</math>-раскрашенный граф. Let <math>k</math> be an integer. A '''<math>k</math>-colored graph''' is…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''<math>k</math>-Colored graph''' - | '''<math>k</math>-Colored graph''' — ''[[k-Раскрашенный граф|<math>\,k</math>-раскрашенный граф]].'' | ||
Let <math>k</math> be an integer. A '''<math>k</math>-colored graph''' is a graph <math>G = (V,E)</math> | Let <math>\,k</math> be an integer. A '''<math>k</math>-colored graph''' is a [[graph, undirected graph, nonoriented graph|graph]] <math>\,G = (V,E)</math> together with a [[vertex]] ''[[coloring, colouring|coloring]]'' which is a mapping <math>\,f: \; V\rightarrow S</math> such that | ||
together with a vertex ''coloring'' which is a mapping <math>f: \; V | |||
\rightarrow S</math> such that | |||
(1) each vertex is colored with one of the colors such that no two | (1) each vertex is colored with one of the colors 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), | ||
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), | |||
(2) <math>|S| = k</math> and each color is used at least once (i.e., <math>f</math> is | (2) <math>\,|S| = k</math> and each color is used at least once (i.e., <math>\,f</math> is surjective). | ||
surjective). | |||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Текущая версия от 13:09, 23 сентября 2014
[math]\displaystyle{ k }[/math]-Colored graph — [math]\displaystyle{ \,k }[/math]-раскрашенный граф.
Let [math]\displaystyle{ \,k }[/math] be an integer. A [math]\displaystyle{ k }[/math]-colored graph is a graph [math]\displaystyle{ \,G = (V,E) }[/math] together with a vertex coloring which is a mapping [math]\displaystyle{ \,f: \; V\rightarrow S }[/math] such that
(1) each vertex is colored with one of the colors 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),
(2) [math]\displaystyle{ \,|S| = k }[/math] and each color is used at least once (i.e., [math]\displaystyle{ \,f }[/math] is surjective).
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.