Minimalne cięcie przez wierzchołki/węzły - bez krawędzi

Question

wszyscy znamy i kochamy s-t algorytmy minimalnego cięcia, ale wszystkie one przecinają krawędzie na wykresie. Czy są jakieś warianty przecinające węzły?

Answer 1

Aby użyć algorytmu minimal-cut-s-t, musisz przekształcić swój wykres w sieć przepływu. Daje to niejawny ukierunkowany wykres (kierunek przepływu do przodu). Możesz użyć tej skierowanej reprezentacji, aby przekształcić wykres w coś, co powinno rozwiązać ten problem. Zasadniczo przekształcasz każdy wierzchołek, V, (z wyłączeniem źródła i zlewu) w dwa wierzchołki, nazywając je A i B. A pobiera wszystkie krawędzie V, B otrzymuje wszystkie krawędzie V. Następnie tworzysz krawędź A -> B o maksymalnej pojemności nieskończoności.

Myślę, że jeśli uruchomisz zwykły algorytm s-t minimal cut, użyjesz tylko krawędzi, które utworzysz. Jedyną zmianą, którą mogę uważać za konieczną, jest sytuacja, w której stopień A jest jeden, może wybrać tę krawędź do przecięcia, ale po prostu wybierz A jako wierzchołek. (To zależy od implementacji algorytmu s-t)

Mam nadzieję, że ma to sens. Nie jestem pewien, czy to działa (tj. Nie mam ochoty wymyślać odpowiedniego dowodu), ale intuicyjnie wyczuwa to. Intuicyjny pogląd, jaki mam, polega na tym, że jeśli wycinamy krawędź "nie werteks", równie dobrze można przeciąć krawędź "wierzchołka", ponieważ ma ona taki sam efekt w.r.t, aby odłączyć wykres.