ABSTRACT
This chapter investigates the optimization of pairings through the use of edge-matchings within a graph, more commonly known as a matching. It describes the graphs to model routing problems or exhaustive problems - spanning trees, shortest networks, Eulerian and Hamiltonian tours. While are still concerned with maximizing or minimizing items, the graph models the chapter focuses on resource requirements for a specific problem. The most common application of matchings is the pairing of people, usually described in terms of marriages. Other applications of a graph matching are task assignment, distinct representatives, and roommate selection. The chapter discusses matchings in graphs that are not bipartite. Matching problems make use of bipartite graphs since the items being matched are usually of two distinct types. The example shown in the chapter illustrates how to model a task assignment problem as a matching in bipartite graph. In most cases, a minimum vertex cover for a bipartite graph requires some vertices from vertex partition.
