Minimalizowanie liczby przejazdów w graf dwudzielny

Question

Następujący problem algorytm przyszło mi do głowy podczas rysowania wykresu czegoś niezwiązanego:

Mamy rysunek płaszczyźnie graf dwudzielny, z rozłącznych zestawów ułożonych w kolumnach, jak pokazano. Jak możemy zmienić kolejność węzłów w każdej kolumnie, aby zminimalizować liczbę przejść przez krawędzie? Wiem, że ten problem jest NP-trudny dla ogólnych wykresów (link), ale czy jest jakaś sztuczka biorąc pod uwagę, że wykres jest dwudzielny?

Jako obserwacji, co jeśli jest jeszcze trzecia kolumna w, który ma tylko krawędzie v? Lub dalej?

Answer 1

Papier On the one-sided crossing minimization in a bipartite graph with large degrees by Hiroshi Nagamochi wspomina, że ​​oryginalny papier na liczbę przekraczania przez Garey i Johnson okazał się również, że minimalizuje liczbę przejazdów krawędziowych jest NP-trudne dla graf dwudzielny. W rzeczywistości, to jest wciąż NP-trudne nawet jeśli powiedziano optymalnej kolejności na jednej kolumnie:

otrzymał graf dwudzielny, 2-warstwowy rysunek polega na umieszczeniu węzły w pierwszym secie węzeł V na linię prostą L1 i umieszczenie węzłów w drugim zestawie węzłów W w linii równoległej L2. Problem polegający na zminimalizowaniu liczby przejść między łukami na dwuwarstwowym rysunku był pierwszym wprowadzonym przez Harary'ego i Schwenka. Problem minimalizacji jednostronnego krzyżowania powoduje, że pojawia się zapytanie o uporządkowanie węzłów w V, które mają być umieszczone na L1, tak aby zmniejszyć do minimum liczbę przejść przez łuk (podczas gdy uporządkowanie węzłów w W na L2 jest podane i naprawione). Zastosowania problemu można znaleźć w układach VLSI i rysunkach hierarchicznych.

Jednakże, dwustronne i jednostronne problemy są pokazane jako NP-trudne przez Garey and Johnson i przez Eadesa i Wormalda, odpowiednio.

Answer 2

Peter de Rivaz wskazał, że jest NP-trudny, ale mimo wszystko, jeśli masz pewne przybliżenia, możesz skorzystać z następującego rozwiązania.

Moja początkowa myśl polegała na zastosowaniu algorytmu opartego na siłach do układania wykresów, ale może być nieco uciążliwe w implementacji. Ale hej, jest taki cudowny program, który może sprawić, że całość zadziała dla ciebie.

Więc po zainstalowaniu tylko przygotować plik z wykresem:

graph G{ 
    {rank=same A B C D E} 
    {rank=same F G H K I J} 

    A -- F; 
    A -- G; 
    A -- K; 
    A -- I; 
    A -- H; 
    A -- J; 

    B -- G; 

    C -- G; 
    C -- J; 

    D -- K; 
    D -- I; 
} 

Run: dot -Tpng yourgraph -o yourgraph.png

i uzyskać coś podobnego do wolnego :-):