Usuń minimalną liczbę wierzchołków, aby rozłączyć wykres

Zastanów się nad niekierowanym wykresem ze źródłem i wierzchołkiem ujścia. Chcemy usunąć minimalną liczbę wierzchołków na tym wykresie, aby odłączyć dowolną ścieżkę między źródłem a ujściem.

Czy możemy to zrobić, używając algorytmu maksymalnego przepływu, minimalnego cięcia?

algorithms graph-theory network-flow

— babysnow
źródło

Powinien działać (zakładam, że wszystkie krawędzie mają tę samą pojemność).

— A.Schulz,

Sprawdź to pytanie w CSTheory

— adrianN

(Ta odpowiedź została pierwotnie podana jako część pytania, w celu weryfikacji).

Moja intuicja mówi mi, że możemy użyć algorytmu maksymalnego przepływu, minimalnego cięcia, aby rozwiązać ten problem:

Zastąp każdą z nieukierunkowanych krawędzi parą skierowanych krawędzi.
Zamień każdy wierzchołek $v$ z dwoma wierzchołkami $v_\text{in}$ i $v_\text{out}$ połączone krawędzią. wszystkie przychodzące krawędzie $v$ będzie związany z $v_\text{in}$ , wszystkie wychodzące krawędzie $v$ będzie związany z $v_\text{out}$ .
Spróbuj znaleźć minimalne cięcie $M$ . Krawędzie $M$ odnoszą się do wierzchołków, które musimy usunąć.

— FrankW
źródło

Nie jest dla mnie jasne, dlaczego miałoby to gwarantować pracę ręczną. Co się stanie, jeśli minimalne cięcie zmodyfikowanego wykresu zawiera niektóre krawędzie, które nie znajdują się między niektórymi

v_{in}

$v_\text{in}$ i

v_{out}

$v_\text{out}$ , ale czy jest ukierunkowana krawędź od kroku 1 rozwiązania? Jak myślisz, dlaczego każde cięcie minimalnego wierzchołka oryginalnego wykresu będzie w korespondencji jeden-do-jednego z cięciem minimalnym zmodyfikowanego wykresu? Myślę, że potrzebny jest dowód.

— DW

Aby wesprzeć odpowiedź FrankW, skorzystaj z poniższych linków, jest artykuł z Abdol – Hossein Esfahanian popierający zamianę nieukierunkowanej krawędzi na dwie skierowane krawędzie. - networkx.github.io/documentation/latest/reference/generated/… - cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

— Pawan Puttaswamy

@awanp, nie podążam za tobą. Oczywiście możesz zastąpić niekierowaną krawędź dwiema skierowanymi krawędziami. Pytanie nie brzmi, czy możesz to zrobić, ale czy po zastosowaniu algorytmu wymienionego na liście FrankW, czy wyjście jest gwarantowane jako prawidłowe rozwiązanie pierwotnego problemu. Nie widzę znaczenia strony man biblioteki NetworkX. Jeśli chodzi o artykuł: ma 14 stron, z 11 różnymi algorytmami, większość bez dowodu poprawności. Czy możesz sprecyzować, która część jest tutaj istotna?

— DW