I opened this pdf expecting to see a section on total unimodularity (TU).
For example, if an undirected graph is bipartite, its node-edge incidence matrix is TU. Any linear program operating on a TU matrix is guaranteed to have an integer solution. This means that any integer program can be relaxed to a linear program. Thus, the problems of bipartite matching and maximum flow can be easily solved using Simplex.
For example, if an undirected graph is bipartite, its node-edge incidence matrix is TU. Any linear program operating on a TU matrix is guaranteed to have an integer solution. This means that any integer program can be relaxed to a linear program. Thus, the problems of bipartite matching and maximum flow can be easily solved using Simplex.
Some of the interesting results are described here: https://en.wikipedia.org/wiki/Unimodular_matrix#Examples_of_...
That wikipedia page does not do a great job at presenting the optimization connection. These slides are better: http://eaton.math.rpi.edu/faculty/Mitchell/courses/matp6620/...