Undirected distances and the postman-structure of graphs (Q1099186): Difference between revisions

We present some properties of the distance function and of shortest paths in \(\pm 1\)-weighted undirected graphs. These extend some basic results e.g. on matchings, on the Chinese postman problem, or on plane multicommodity flows. Furthermore, distances turn out to be efficient tools to generalize the matching-structure of graphs to a structure related to subgraphs having only parity constraints on their degrees, (these are called joins or postman sets), a problem posed by Lovàsz and Plummer. The special cases include the generalization of the matching- structure of graphs to the weighted case. The main result of the paper is a good characterization (linear in the number of edges), conjectured by A. Frank, of the minimum weights of paths from a fixed vertex of an undirected graph without negative circuits. This result contains the well-known minimax theorems on minimum ``odd joins'' and maximum packings of ``odd cuts'' (namely Lovàsz's theorem on half integer packings and its sharpening by Seymour and later by Frank, Tardos) and strengthens them by constructing a ``canonical'' maximum packing of odd cuts with favourable properties. This packing of odd cuts turns out then to be characteristic for the structure of minimum odd joins. Using these, a Gallai-Edmonds type structural description of minimum odd joins is worked out. (The generalization of the Kotzig- Lovàsz canonical partition will appear in a forthcoming paper.) Briefly, distances in \(\pm\)-weighted graphs make possible to treat some properties of matchings themselves in a more compact way, and to generalize them providing new results on some other interesting special cases of \(\pm\)-weighted graphs as well. This technique is worked out in the present paper.