Coupling in a Graph in less than 128 words

A coupling is a set of ridges two to two independent: they do not share peaks.

Example of coupling in a graph: the 2 red stops do not share peaks (2 to 2 independent)

Perfect coupling: Each top of the graph is in exactly one stop of coupling

Example of perfect coupling in a graph

A perfect graph has an even number of peaks (the reciprocal is not true)

A perfect coupling is a coupling of maximum size (impossible to enlarge, you can not pair more), the reciprocal is not true.

Example of maximum coupling but no max size (i.e. it is possible to do for example a coupling with 3 stops)

Example of use: In a logistics company, employees have one or more permits allowing them to drive a certain type of vehicle. The problem can be represented in a graph with the company's employees and vehicles as its top. To solve the problem you then have to find a pairing of max size.

Gluttonous algorithm to find maximum coupling:

Step 1: A stop is randomly selected and stored in a copy of the graph (left)

Selecting the stop

Step 2: Stop stops that are incidental at both summits are removed and another stop is selected randomly

Step 3: Stop stops that are incidental at both peaks are removed, resulting in maximum coupling