4501
правка
Радиораскраска в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 13:34, 12 апреля 2016
, 12 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
Дано: граф G(V, E). | Дано: граф G(V, E). | ||
Требуется: найти функцию <math>\phi : V \to \{ 1, ..., \infty \} \;</math>, называемую ''k-раскраской | Требуется: найти функцию <math>\phi : V \to \{ 1, ..., \infty \} \;</math>, называемую ''k-раскраской'' графа G, такую, что <math>\forall u, v \in V, x \in \{0, 1, ..., k \} \;</math>: если <math>d(u, v) \ge k - x + 1 \;</math>, то <math>| \phi(u) - \phi(v)| = x \;</math>. | ||
Цель: Пусть <math>| \phi (V) | = \lambda_{ \phi } \;</math>. Тогда <math>\lambda_{ \phi } \;</math> - ''количество цветов'', фактически используемых <math>\phi \;</math> (обычно называемое ''порядком'' G относительно <math>\phi \;</math>). Количество <math>v_{ \phi } = max_{v \in V } \phi (v) - min_{ u \in V } \phi (u) + 1 \;</math> обычно называется ''диапазоном'' графа G относительно <math>\phi \;</math>. Функция <math>\phi \;</math> удовлетворяет одной из следующих целей: | Цель: Пусть <math>| \phi (V) | = \lambda_{ \phi } \;</math>. Тогда <math>\lambda_{ \phi } \;</math> - ''количество цветов'', фактически используемых <math>\phi \;</math> (обычно называемое ''порядком'' G относительно <math>\phi \;</math>). Количество <math>v_{ \phi } = max_{v \in V } \phi (v) - min_{ u \in V } \phi (u) + 1 \;</math> обычно называется ''диапазоном'' графа G относительно <math>\phi \;</math>. Функция <math>\phi \;</math> удовлетворяет одной из следующих целей: | ||