4501
правка
Радиораскраска в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 19:29, 11 апреля 2016
, 11 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
• минимальный порядок: <math>v_{ \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-раскраски называется задачей ''радиораскраски''. | ||
| Строка 31: | Строка 31: | ||
Требуется: найти функцию <math>\Phi : V \to N^* \;</math>, такую, что <math>| \Phi (u) - \Phi (v) | \ge 2 \;</math>, если d(u, v) = 1, и <math>| \Phi (u) - \Phi (v) | \ge 1 \;</math>, если d(u, v) = 2. | Требуется: найти функцию <math>\Phi : V \to N^* \;</math>, такую, что <math>| \Phi (u) - \Phi (v) | \ge 2 \;</math>, если d(u, v) = 1, и <math>| \Phi (u) - \Phi (v) | \ge 1 \;</math>, если d(u, v) = 2. | ||
Цель: наименьшее возможное число (порядок), необходимое для радиораскраски G, обозначим как <math>X_{order}(G) \;</math>. Наименьшее возможное число <math> | Цель: наименьшее возможное число (порядок), необходимое для радиораскраски G, обозначим как <math>X_{order}(G) \;</math>. Наименьшее возможное число <math>max_{v \in V } \phi (v) - min_{ u \in V } \phi (u) + 1 \;</math> (диапазон), необходимое для радиораскраски G, обозначим как <math>X_{span}(G) \;</math>. Функция <math>\Phi \;</math> удовлетворяет одному из следующих условий: | ||
• минимальный диапазон для радиораскраски: | • минимальный диапазон для радиораскраски: <math>\Phi \;</math> находит минимальный диапазон, т.е. <math>\lambda_{ \Phi } = X_{span}(G) \;</math>; | ||
• минимальный порядок для радиораскраски: | • минимальный порядок для радиораскраски: <math>\Phi \;</math> находит минимальный порядок <math>v_{ \Phi} = X_{order}(G) \;</math>; | ||
• минимальный порядок диапазона для радиораскраски: | • минимальный порядок диапазона для радиораскраски: находим минимальный диапазон, и затем среди всех присваиваний по минимальному диапазону <math>\Phi \;</math> находит минимальный порядок. | ||
• минимальный диапазон порядка для радиораскраски: | • минимальный диапазон порядка для радиораскраски: находим минимальный порядок, и затем среди всех присваиваний по минимальному порядку <math>\Phi \;</math> находит минимальный диапазон. | ||
Родственная радиораскраске задача относится к квадрату графа G, который определяется следующим образом: | Родственная радиораскраске задача относится к квадрату графа G, который определяется следующим образом: | ||