All geek questions in one place

Calculation of the minimum section of the graph without back edges

I know that you can use a Max-Flow algorithm like Ford-Fulkerson and find a Min-Cut with the Max-Flow / Min-Cut theorem. However, this is not exactly the type of Min-Cut I need to calculate.

I want to find Min-Cut of G into sets S and T, where no edges from T to S .

This sample graph finds the minimum incision (250 in magnitude), but the result has an edge from T to S (red).

enter image description here

Does anyone know if there is an existing algorithm to solve this problem? Or if there is a way to change my flow network so that I can use something like Ford-Fulkerson?

+4
source share
1

, : . , , S T, .

+1

Source: https://habr.com/ru/post/1537733/

More articles:


All Articles