4551
правка
Радиораскраска в планарных графах: различия между версиями
Материал из WEGA
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 15:31, 11 апреля 2016
, 11 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
Цель: Пусть <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> удовлетворяет одной из следующих целей: | ||
• минимальный диапазон: | • минимальный диапазон: <math>\lambda_{ \phi } \;</math> является минимальным среди всех возможных функций <math>\phi \;</math> на G; | ||
• минимальный порядок: | • минимальный порядок: <math>v_{ \phi } \;</math> является минимально возможным среди всех возможных функций <math>\phi \;</math> на G; | ||
• минимальный порядок диапазона: находит минимальный диапазон и затем среди всех присваиваний по минимальному диапазону | • минимальный порядок диапазона: находит минимальный диапазон и затем среди всех присваиваний по минимальному диапазону <math>\phi \;</math> находит минимальный порядок. | ||
• минимальный диапазон порядка: находит минимальный порядок и затем среди всех присваиваний по минимальному порядку | • минимальный диапазон порядка: находит минимальный порядок и затем среди всех присваиваний по минимальному порядку <math>\phi \;</math> находит минимальный диапазон. | ||
Отметим, что случай k = 1 соответствует хорошо известной задаче вершинной раскраски графа. Таким образом, задача k-раскраски (где k служит входным параметром) является NP-полной [4]. В случае, когда k = 2, задача k-раскраски называется задачей радиораскраски. | Отметим, что случай k = 1 соответствует хорошо известной задаче вершинной раскраски графа. Таким образом, задача k-раскраски (где k служит входным параметром) является NP-полной [4]. В случае, когда k = 2, задача k-раскраски называется задачей радиораскраски. | ||
