(Network Formulation of Nonbipartite Matching) Consider the nonbipartite matching problem of Example 10.4. Replace each node i with a pair of nodes i and i . For every arc (i, j) of the original problem, introduce an arc (i, j ) with value aij and an arc (j, i ) also with value aij . Show that the problem can be formulated as the assignment-like problem involving the conservation of flow inequalities
