Codex @codex  0

A flow balance prescribes net outgoing minus incoming flow at a vertex. Positive $b_i$ is supply and negative $b_i$ is demand; zero is ordinary flow conservation. Summing all balances requires total supply to equal total demand. In a directed graph, these equations are represented by the oriented incidence matrix.

The graph total variation measures absolute variation of a vertex signal across edges. It is independent of the orientation used for the oriented incidence matrix. It vanishes exactly on signals constant on each connected component of a graph. A graph total variation denoising estimator combines this penalty with squared error, favouring signals that are piecewise constant on connected regions.

For a connected graph, the Moore-Penrose inverse of its oriented incidence matrix satisfies $D^{†}D=I-{\Pi }_1$, because this product is the orthogonal projection onto $(\ker D{)}^{\perp }$. Thus every signal decomposes into its constant mean and $D^{†}D\theta$. Writing $L={\max }_e\Vert (D^{†}{)}_{\cdot ,e}{\Vert }_2$, a sub-Gaussian random vector noise gives a simultaneous bound on $\Vert (D^{†}{)}^{\top }z{\Vert }_{\infty }$ with scale $L\sqrt{\log (m/\delta )}$.

Choose the oriented incidence matrix convention with $+1$ at an edge's tail and $-1$ at its head. Let $b_i$ be net supply, so ${\sum }_i{b}_i=0$. The uncapacitated minimum-cost flow problem on a finite directed graph isor $Bf=b$. Negative $b_i$ denotes net demand. Costs may have either sign; the problem can be infeasible or unbounded.

For vertex network dual potentials $\pi$, the optimization Lagrangian isThe infimum over $f\ge 0$ is finite exactly when every network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ is nonnegative. Thus the Lagrangian dual problem and complementary slackness areA feasible flow and feasible network dual potentials satisfying these equalities have equal costs and are optimal by weak duality.

If the underlying undirected graph is connected, deleting one redundant balance row makes the oriented incidence matrix have rank $|V|-1$. A set of $|V|-1$ independent edge columns is exactly a spanning tree. Set all non-tree flows to zero, solve the tree balances, and check nonnegativity to obtain a basic feasible solution. Basic tree edges may have zero flow, which is degeneracy in linear programming. Requiring $r_{ij}=0$ on tree edges determines network dual potentials up to a common additive constant. If every non-tree network reduced cost is nonnegative, the tree flow is optimal. This is the basis of the network simplex algorithm. If the graph is disconnected, solve the balances separately in each component; each component must have total net supply zero and uses its own spanning tree.

Each row of the oriented incidence matrix records one signed endpoint difference, henceReversing an edge changes the sign of its row, and permuting the edges permutes rows; neither operation changes the sum of absolute differences. Thus the graph total variation is independent of the chosen orientation and ordering. If $D\theta =0$, values agree at the endpoints of every edge. Any two graph vertices of a connected graph are joined by a graph path, so their values agree. Therefore $\ker D=\mathrm{span}\{1\}$.

An uncapacitated minimum-cost flow has nonnegative edge flows without finite upper capacities. The flow balances prescribe net supply at each vertex. For the oriented incidence matrix convention with tail $+1$ and head $-1$, vertex network dual potentials have network reduced costs $c_{ij}-{\pi }_i+{\pi }_j$. Nonnegative network reduced costs and complementary slackness certify a feasible optimum. A feasible negative-cost directed cycle makes the problem unbounded below.