4501
правка
Радиораскраска в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 19:34, 11 апреля 2016
, 11 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
Родственная задача заключается в раскраске квадрата графа G, <math>G^2 \;</math>, таким образом, чтобы никакие две соседние вершины в G2 не были раскрашены в один цвет. Целью является использование минимального числа цветов, которое обозначается <math>\chi (G^2) \;</math> и называется [[хроматическое число|хроматическим числом]] квадрата графа G. В [5, 6] было впервые замечено, что для любого графа G значение <math>X_{order}(G) \;</math> совпадает с (вершинным) хроматическим числом <math>G^2 \;</math>, т.<math>е. X_{order}(G) = \chi (G^2) \;</math>. | |||
== Основные результаты == | == Основные результаты == | ||