Исключение сторон в ориентированном циклическом графе или Турнире (графе)

Question

Я хотел алгоритм, чтобы исключить стороны циклического ориентированного графа или, в основном, Турнир, и вывести структуру дерева с минимальным количеством сторон.

Исключение должно основываться на весе сторон, как описано ниже в качестве простого примера из реальной жизни.

Если есть три друга A,B,C. Возьмите сценарий заимствования и возврата денег между собой.

Лицо А должно перевести Лицо Б - 10 долларов. Человек B должен перевести Человека C - 20 долларов. Человек С должен перевести Человека А - 20 долларов.

В конечном счете, чтобы свести к минимуму количество переводов между собой, мы можем изменить вышеупомянутое значение на что-то вроде "Лицо Б переведет Лицо А - 10 долларов", и все решено.

Я ищу какой-нибудь алгоритм, который будет работать для любого количества узлов, когда указан вес каждой стороны и направления.

Учитывая, что график можно переставить и высоки шансы на то, что граф может быть " Турниром", где каждый узел связан со всеми узлами графа, я выбрал бы лучший подход.

Спасибо заранее Sudhaker

Answer 1

n - 1 ребра довольно легко получить. Сначала вычислите "чистую стоимость" каждого, поместите заемщиков в один список, поместите кредиторов в другой, а затем повторно сделайте перевод от заемщика в начале строки к кредитору, удаляя одного или обоих, если они насыщены (возвращены в ноль).

Предыдущий алгоритм является 2-аппроксимацией. Минимизация количества переносов означает максимизацию количества переносов с двойной насыщенностью, что является проблемой, подобной ранцу, которая, по крайней мере, слабо NP-сложная. Существует динамическая программа с экспоненциальным временем, которая может подойти для малых n (наивный больше похож на n^n).