Given a minimum-cost flow problem, how could I go about demonstrating that a specific solution (as sets of basic and non-basic (!) arcs that build a rooted spanning tree for a given graph) is basic and feasible for the problem?
Update: the MCF problem has a variable number of divergences, for the nodes – some require more flow than others, some generate it and through the remaining ones the flow only transit. Also, how does proving the feasibility of a solution and whether or not it is basic change with and without bound constraints?
As per the feasibility, I figure it could be pretty straightforward: a solution is feasible as long as it satisfies all constraints, I may dare saying for any Operation Research problem.
For a MCF problem, as long as the strongly connected graph built with the arcs in the given solution create a rooted spanning tree free of any cycles, I would claim the solution is indeed feasible.
How about proving the given solution is basic, however?
Given a linear problem, a solution is basic if it is indeed possible to build a matrix $B \subset A$ ($A$ being the matrix of technological coefficients) with at least $m$ (where $m$ is the number of constraints for the given LP) linearly independent columns. Since the network simplex works similarly to the "classical" simplex, would the statement above be sufficient to prove a solution is indeed basic?