Если ли какой-нибудь алгоритм поиска максимального потока при условии что вершины тоже имеют вес
1 ответ
Да, для этого каждая вершина v
расщепляется на две:
v-
- вершина, в которую будут входить все ребра, которые входили в вершину v
v+
- вершина, из которой будут выходить все ребра, которые выходили из вершины v
А также в граф добавляется ребро (v-, v+)
с пропускной способностью, равной пропускной способности исходной вершины v
. Затем решается обычная задача нахождения максимального потока.