Jak nazywa się ten problem z grafem skierowanym?

16

Wykonaj ukierunkowany wykres gdzie krawędzie są ozdobione naturalną liczbą. Chcemy zestawu wszystkich ścieżek między dwoma wierzchołkami v 1 i tak aby każda kolejna krawędź ścieżki była ozdobiona liczbą naturalną, która jest większa niż liczba naturalna dekorująca poprzednią krawędź.Gv 2P.v1v2)

Przykładem może być rozkład jazdy autobusów lub pociągów. Jeśli próbujesz ustalić różne trasy między dwoma miastami na podstawie transferów między stacjami. (Nie możesz wsiąść do drugiego pociągu zaplanowanego do odjazdu przed przybyciem pierwszego).

Nieformalnie nazywam to „grafem zaplanowanym”. Ale nie wiem, jak nazywa się to w literaturze.

Interesujące są również wszelkie odniesienia do algorytmów z tym związanych.

ds.algorithms reference-request graph-algorithms terminology Obrabować
źródło
umiarkowanie spokrewnione: cstheory.stackexchange.com/questions/5849/...
Artem Kaznatcheev
1
Jeśli weźmiesz pod uwagę wykres liniowy i zorientujesz krawędzie od węzła o niższym numerze do węzła o wyższym numerze, otrzymasz DAG G ′ . I odwrotnie, w ten sposób można uzyskać dowolną acykliczną orientację dowolnego wykresu liniowego. Dlatego twój problem wydaje się zasadniczo równoznaczny z następującym problemem: biorąc pod uwagę acykliczną orientację wykresu liniowego, znajdź wszystkie skierowane ścieżki, które łączą daną parę węzłów. Ale nie jestem pewien, czy własność bycia wykresem liniowym naprawdę tu pomaga ...? solsol′
Jukka Suomela,

Odpowiedzi:

14

O ile mi wiadomo, problem ten nazywa się czasem „ścieżkami nie zmniejszającymi się” i był badany od lat 50. Zobacz na przykład ten artykuł: GJ Minty. Wariant dotyczący problemu najkrótszej trasy, Operations Research, 6 (6): 882–883, 1958.

Wersja problemu, który prosi o ścieżkę nie zmniejszania z st

dziewice
źródło