What's the optimal matching?

# Matchings of optimal Weight

We extend the example of matching students to appropriate jobs by introducing preferences. Now, we aim to find a matching that will fulfill each students preference (to the maximum degree possible).

Finding matchings between elements of two distinct classes is a common problem in mathematics. In this case, we consider weighted matching problems, i.e. we look for matchings with optimal edge weights.

## Legend

 Node Edge

## Which graph do you want to execute the algorithm on?

### Modify it to your desire:

• Double click in the area of one of the partitions, in order to add a vertex to that partition. You can create up to 8 nodes in each partition.
• In order to create an edge, first click on the origin node, then on the destination node.
• You can only create edges between separate partitions. You can change the weight of an edge by double clicking the middle of the edge and entering the new weight.
• Right-clicking will delete edges or nodes.

A occured when reading from file: the contents:

## Legend

 Matched Node Matching Edge

## Current State of the Algorithm

BEGIN

initialize labels

WHILE matching is not complete DO

find a root of an alternating path

try to find alternating path

in equality graph

THEN update labels

END

increase matching

END

END

Matching S T

## If you switch tabs, the execution will be terminated.

You can open another browser window to read the description in parallel.

## Legend

 Matched Node Matching Edge

## Test your Knowledge: What would the algorithm do?

BEGIN

initialize labels

WHILE matching is not complete DO

find a root of an alternating path

try to find alternating path

in equality graph

THEN update labels

END

increase matching

END

END

Matching S T

## If you switch tabs, the execution will be terminated.

You can open another browser window to read the description in parallel.

## Legend

 Matched Node Matching Edge

## Test your Knowledge: What would the algorithm do?

BEGIN

initialize labels

WHILE matching is not complete DO

find a root of an alternating path

try to find alternating path

in equality graph

THEN update labels

END

increase matching

END

END

Matching S T

## Task is terminated if the tab is changed.

You can open another browser window for reading the description in parallel.