MAV - Matching Algorithm Visualiser

Welcome to

by Yasser Oozeer

Left-click
Add vertex +
Set capacity

Click-and-drag
Add edge

Right-click
Remove vertex/edge

Ctrl + Click-and-drag
Move vertex

Start

Left-click
Add vertex +
Set capacity

Click-and-drag
Add edge

Right-click
Remove vertex/edge

Ctrl + Click-and-drag
Move vertex

(This panel is interactive)

Start animation

Reposition nodes

Clear graph

Edit graph

Random (right-click: custom)

Less detailed animation

A bipartite graph is a graph that can be partitioned into two sides so that every edge joins a vertex from one side to the other.

A matching satisfies the property that each vertex is incident to a number of edges limited by its capacity.

A maximum matching in the graph is a matching that contains the largest number of edges.

An vertex is exposed if it is not matched.

An alternating path is a path that comprises of edges in a matching and edges not in the matching alternately.

An augmenting path is an alternating path which starts and ends at exposed vertices.

Theorem: A matching is of maximum cardinality if and only if it admits no augmenting path.

Swipe