Matching

Basic concepts regarding maximum matching

What it is a graph?

Graph is a way to represent relationships between objects. In computation, it uses points to represent objects and lines between the ones that possess a relationships among them. The points could be computers and the lines could be the cables that make the connection between them. Another example is: the points representing people and the lines representing the friendship between them. An example of a relationship is represented in the figure below:

Figure: Representation of a graph.

What it is a maximum matching?

A maximum matching is the biggest set of relationships (lines) that do not possess common points in a graph. For example: if the points represent computers and if the lines represent the connection between them and assuming that a computer can only communicate with only one another computer at a given instant, then the maximum matching would be the maximum number of communications between computers in instant. Given the relationship of the previous figure, a possible maximum mating would be the relationship represented in the below. The marked lines represent the lines that had been chosen to belong to the maximum matching.

Figure: Representation of a maximum matching. The selected edges are the ones that belongs to the maximum matching.