  Minimum spanning trees and forests are powerful sparsification techniques
that remove cycles from weighted graphs to minimize total edge weight while
preserving node connectivity. They have applications in computer science,
network science, and graph theory. Despite their utility and ubiquity, they
have several limitations, including that they are only defined for undirected
networks, they significantly alter dynamics on networks, and they do not
generally preserve important network features such as shortest distances,
shortest path distribution, and community structure. In contrast, distance
backbones, which are subgraphs formed by all edges that obey a generalized
triangle inequality, are well defined in both directed and undirected graphs
and preserve those and other important network features. The backbone of a
graph is defined with respect to a specified path-length operator that
aggregates weights along a path to define its length, thereby associating a
cost to indirect connections. The backbone is the union of all shortest paths
between each pair of nodes according to the specified operator. One such
operator, the max function, computes the length of a path as the largest weight
of the edges that compose it (a weakest link criterion). It is the only
operator that yields an algebraic structure for computing shortest paths that
is consistent with De Morgan's laws. Applying this operator yields the
ultrametric backbone of a graph in that (semi-triangular) edges whose weights
are larger than the length of an indirect path connecting the same nodes (i.e.,
those that break the generalized triangle inequality based on max as a
path-length operator) are removed. We show that the ultrametric backbone is the
union of all minimum spanning forests in undirected graphs and provides a new
generalization of minimum spanning trees to directed graphs.
