## Optimized Match

#### A Simple Graph

In this graph there are five nodes and four edges. Note that nodes may have any number of edges connected to them, including zero.

#### Graphs for KPD Match

In a graph used for kidney donor matching, each **node** represents
an incompatible donor/recipient pair, and each **edge**
represents a possible match.

Optimized Match is based on a matching algorithm
from graph theory, which is a branch of applied mathematics. Graph
theory deals with the concept of a **graph**, which is a collection of
**nodes** and **edges** connecting the nodes (see the example graph
drawn on the right).

For the problem of Kidney Paired Donation, we first construct a graph where each node indicates an incompatible donor/recipient pair, and each edge indicates a possible match between the two nodes that it connects. This graph can be constructed by entering blood type, antibody, and HLA information for each pair (node) into a computer. The computer can then determine which pairs are compatible (which matches are possible) and draw edges between these pairs.

Once the graph is constructed and all possible matches are determined, the Optimized Match is run.
It compares every possible combination of matches (every **feasible solution**)
to determine the **best solution** possible for the criteria provided.