Раскраска пути - Path coloring

В теория графов, раскраска пути обычно относится к одной из двух проблем:

• Проблема раскраски (мульти) набор из пути ${displaystyle R}$ в графике ${displaystyle G}$, таким образом, что любые два пути ${displaystyle R}$ которые разделяют преимущество в ${displaystyle G}$ получить разные цвета. Набор ${displaystyle R}$ и график ${displaystyle G}$ предоставляются на входе. Эта формулировка эквивалентна раскраска вершин то граф конфликтов набора ${displaystyle R}$, т.е. граф с множеством вершин ${displaystyle R}$ и ребра, соединяющие все пары путей ${displaystyle R}$ которые не пересекаются по ребрам относительно ${displaystyle G}$.
• Задача раскраски (в соответствии с приведенным выше определением) любого выбранного (мульти) набор ${displaystyle R}$ путей в ${displaystyle G}$, таких, что множество пар концевых вершин путей из ${displaystyle R}$ равно некоторому множеству или мультимножеству ${displaystyle I}$, называется набор запросов. Набор ${displaystyle I}$ и график ${displaystyle G}$ предоставляются на входе. Эта проблема является частным случаем более общего класса задач маршрутизации графов, известных как планирование звонков.

В обеих вышеупомянутых задачах цель обычно состоит в том, чтобы минимизировать количество цветов, используемых при раскраске. В разных вариантах раскраски дорожек, ${displaystyle G}$ может быть простой график, диграф или мультиграф.

Рекомендации

• [1] Сложность раскраски пути и планирования звонков Томас Эрлебах и Клаус Янсен
• [2] Сборник задач оптимизации NP Автор: Вигго Канн (задача: раскраска минимального пути)