graf skierowany z max indegree z wierzchołka

Question

starałem się spojrzeć na kilka zastosowań sieci przepływu, gdy natknąłem się na ten problem:

Zaczynamy graf skierowany, G = (V,E). Musimy dodać więcej krawędzi do wykresu, abyśmy mieli \forall u,v \in V, e = (u -> v) or e = (v -> u) but not both. tj. chcemy dodać więcej krawędzi do wykresu, aby każda para wierzchołków na wykresie była ze sobą połączona (z krawędzią wychodzącą lub krawędzią wejściową, ale nie z obu). Łącznie będziemy mieć krawędzie |V||V-1|/2. Podczas budowania tego wykresu musimy upewnić się, że indegree danego wierzchołka, na przykład w, jest maksymalnym wśród wszystkich wierzchołków wykresu (jeśli jest to możliwe, biorąc pod uwagę pierwotny wykres). Zwróć uwagę, że nie możemy zmienić orientacji krawędzi na oryginalnym wykresie.

Próbuję go rozwiązać za pomocą przepływu sieci, budując sieć bez wierzchołka w (oraz z 2 nowych wierzchołków dla źródła, s i tonąć, t). Nie jestem jednak pewien, jak przedstawić przepustowość i kierunek przepływu na nowym wykresie, aby uprościć problem z przepływem sieci w celu znalezienia orientacji krawędzi na wykresie. Może to, co robię, jest złe, ale właśnie napisałem, żeby ktoś mógł się o tym dowiedzieć.

Answer 1

Kiedy atakuję ten rodzaj problemu, staram się zapisać program matematyczny, a następnie go masować. Oczywiście, powinniśmy zorientować wszystkie brakujące krawędzie angażując w kierunku w. Niech d będzie wynikiem w-stopni w. Dla wszystkich różnych i, j, niech x_{ij} = 1, jeśli łuk i-> j pojawi się w roztworze i niech x_{ij} = 0, jeśli pojawi się łuk j-> i.

forall j. sum_i x_{ij} <= k 
forall i <> j. x_{ij} = 1 - x_{ji} 
forall i <> j. x_{ij} in {0, 1} 

x_{ij} Przepisz używać tylko gdybym < j.

(*) forall j. sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) <= k 
forall i < j. x_{ij} in {0, 1} 

Now (*) zaczyna przypominać ograniczeń konserwatorskich, a pojawia się raz ujemnie i dodatnio raz każda zmienna. Zmieńmy nierówność na równość.

(*) forall j. x_{si} + sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) = k 
       ^^^^^^           ^
forall i < j. x_{ij} in {0, 1} 
forall i. x_{si} >= 0 
^^^^^^^^^^^^^^^^^^^^^ 

Jesteśmy prawie całą drogę do LP przepływu - po prostu trzeba oczyścić stałych 1 i k. Pozwolę ci poradzić sobie z resztą (wiąże się to z wprowadzeniem t).