Раскраска пути

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

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

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

Ссылки

• «Сложность раскраски путей и планирования вызовов», Томас Эрлебах и Клаус Янсен
• Сборник задач оптимизации NP Вигго Канна (задача: минимальная раскраска пути)