Theory and Application of Graphs
==========================================================================
Chapter
4
Flows
and Connectivity
As we have seen in the preceding chapters, the most basic property a graph possesses is that of being connected. A
most basic concept to study connectedness of a connected graph is connectivity of the graph. The most sensitive parameters measuring
the connectivity of a graph are (vertex-) connectivity and edge-connectivity of the graph. We will, in this chapter, discuss
these two parameters in two its local and global aspects.
Menger's theorem is the best-known, the most classical and fundamental result on local connectivity of a graph, which is the
basis of almost every proof of connectivity properties, and thus is one of the cornerstones of graph theory. We will present
Menger's theorem and its edge version, deduced from the max-flow min-cut theorem of Ford and
Fulkerson. We will point out the
equivalence of these theorems. Then we discuss the relations among the global (vertex-)connectivity, the global edge-connectivity and
the minimum degree of a graph as well, and establish a sufficient and necessary condition for a graph to be
k-connected (or k-edge-connected), due to Menger and Whitney.
The analytical method of network flow is an important one in graph theory. In application part of this chapter, we will make use of
theory of flows and graphic spaces to describe three efficient algorithms,
labeling method, Klein's algorithm and Edmonds-Johnson's algorithm, for solving the designs of transport
schemes, optimal transport schemes, and the Chinese Postman Problem, respectively. Lastly, we will introduce a famous
combinatorial problem, squared rectangles, whose solution needs
the help of theory of flows.
|
