Радиораскраска в планарных графах: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Определение 1 (задача k-раскраски) | '''Определение 1 (задача k-раскраски)''' | ||
Дано: граф G(V, E). | Дано: граф G(V, E). | ||
| Строка 22: | Строка 22: | ||
• минимальный диапазон порядка: находит минимальный порядок и затем среди всех присваиваний по минимальному порядку <math>\phi \;</math> находит минимальный диапазон. | • минимальный диапазон порядка: находит минимальный порядок и затем среди всех присваиваний по минимальному порядку <math>\phi \;</math> находит минимальный диапазон. | ||
Отметим, что случай k = 1 соответствует хорошо известной задаче вершинной раскраски графа. Таким образом, задача k-раскраски (где k служит входным параметром) является NP-полной [4]. В случае, когда k = 2, задача k-раскраски называется задачей радиораскраски. | Отметим, что случай k = 1 соответствует хорошо известной задаче [[вершинная раскраска|вершинной раскраски]] графа. Таким образом, задача k-раскраски (где k служит входным параметром) является NP-полной [4]. В случае, когда k = 2, задача k-раскраски называется задачей ''радиораскраски''. | ||
Определение 2 (задача радиораскраски) (Radiocoloring Problem, RCP [7]) | '''Определение 2 (задача радиораскраски) (Radiocoloring Problem, RCP [7])''' | ||
Дано: граф G(V, E). | Дано: граф G(V, E). | ||