4446
правок
Радиораскраска в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 14:46, 11 апреля 2016
, 11 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
Требуется: найти функцию <math>\phi : V \mapsto \{ 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 \mapsto \{ 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> удовлетворяет одной из следующих целей: | ||
• минимальный диапазон: Хф является минимальным среди всех возможных функций ' на G; | • минимальный диапазон: Хф является минимальным среди всех возможных функций ' на G; | ||