Как называется этот тип задачи ориентированного графа?

Возьмем ориентированный граф края которого украшены натуральным числом. Нам нужно множество всех путей между двумя вершинами и , чтобы каждое последующее ребро в пути было украшено натуральным числом, которое больше натурального числа, украшающего предыдущее ребро. $G$ $P$ $v_1$ $v_2$

Заявка на это будет расписание автобусов или поездов. Если вы пытаетесь определить разные маршруты между двумя городами на основе пересадок между станциями. (Вы не можете сесть на второй поезд, запланированный отъезд до того, как прибудет первый.)

Я неофициально называю это «запланированный график». Но я не знаю, как это называется в литературе.

Любые ссылки на алгоритмы, связанные с этим, также представляют интерес.

ds.algorithms reference-request graph-algorithms terminology обкрадывать
источник

Слегка

Артем Казнатчеев

Если вы рассмотрите линейный граф

и ориентируете ребра от узла с меньшим номером к узлу с большим номером, вы получите DAG

. И наоборот, любая ациклическая ориентация любого линейного графа может быть получена таким образом. Следовательно, ваша задача, по-видимому, по существу равна следующей задаче: учитывая ациклическую ориентацию линейного графа, найдите все направленные пути, которые соединяют данную пару узлов. Но я не уверен, действительно ли здесь помогает свойство быть линейным графиком ...?

G

$G$

G^{'}

$G'$

Юкка Суомела

Как называется этот тип задачи ориентированного графа?

Ответы: