측면 순환주기 그래프 또는 토너먼트에서 제거 (그래프)

Question

나는 순환 지향 그래프 또는 대부분 토너먼트의 측면을 제거하고 최소 수의 측면을 가진 트리 구조의 구조를 출력하는 알고리즘을 원했습니다.

제거는 측면의 무게를 기준으로해야하며 아래 실제 간단한 예에서 설명합니다.

친구 A, B, C가 세 명인 경우. 서로간에 돈을 환불 & 빌려의 시나리오를 가져 가라.

사람 A는 사람 B를 $ 10로 이전해야합니다. 사람 B는 사람 C - $ 20를 전학시켜야합니다. 사람 C는 사람 A - $ 20를 전학시켜야합니다.

서로 간의 이동 횟수를 최소화하기위한 최종 합의에서 "사람 B는 사람 A - 10 달러를 이체 할 것"과 같이 모든 것을 재배치 할 수 있으며 모든 것이 정산됩니다.

각 측면과 방향의 무게가 주어지면 노드 수에 관계없이 작동하는 알고리즘을 찾고 있습니다.

그래프가 재 배열 될 수 있고 그래프가 각 노드가 그래프의 모든 노드에 연결된 "Tournament"일 가능성이 높다고 가정하면 내가 따르는 최상의 방법이 될 것입니다. 사전 Sudhaker

Answer 1

n은에

감사합니다 - 1 가장자리가 얻을 매우 쉽습니다. 먼저 모든 사람의 "순자산"을 계산하고, 차용자를 하나의 목록에 넣고, 대출자를 다른 사람에 넣고, 차용자로부터 차용자에게 반복적으로 이체하여 대출자에게 포워딩합니다. 0으로).

앞의 알고리즘은 2- 근사 식입니다. 전송 횟수를 최소화하면 이중 포화 전송 횟수를 최대화 할 수 있습니다. 이는 최소한 NP 힘든 배낭 모양의 문제입니다. 작은 n (naive는 n^n과 비슷합니다)에 적합한 지수 시간 동적 프로그램이 있습니다.