Summary: We show that in any digraph on an underlying connected graph with non-negative weights on its edges, there is a Majority Spanning Tree for which sum of weights of edges of a fundamental cutset, running along each edge of the spanning tree determining the cutset, is not less than sum of those running in opposite direction. Similarly, there is a Majority Cotree, each fundamental cycle of which has non-negative weight. We further prove simultaneous existence of majority spanning trees and majority cotrees in any non-negative weighted digraph. We have shown how these structures can be used to solved scheduling transports by minimizing sum of weighted connection times, ranking round-robin tournaments by minimizing number of upsets, in settling multiple debts and in construction of transport networks with unbalanced road capacity.
For the entire collection see [Zbl 1470.68028].