Pojmy
Bipartitní graf
Graf se nazývá
bipartitní, jestliže jeho množinu vrcholů je možno rozdělit na dvě disjunktní množiny
M a
N tak, že pro všechny hrany z
E platí, že jeden její koncový vrchol leží v
M a druhý v
N.
Párování
Množina hran
P grafu se nazývá
párování, jestliže žádné dvě hrany v
P nemají společný koncový vrchol.
Úplné párování
Párování
P nazývá
úplné, jestliže každý vrchol je koncovým vrcholem některé hrany v
P.
Největší a maximální párování
Největší párování v grafu
G je takové, že v
G neexistuje jiné párování s větším počtem hran.
Maximální párování v grafu
G je takové, že v
G neexistuje žádná hrana, kterou by bylo možno k párování přidat.
Bohužel maximální párování nemusí být největší párování.
Alternující cesta
Alternující cesta v grafu vzhledem k párování
P je taková cesta, na které se pravidelně střídají hrany, které do párování
P patří a které do
P nepatří.
Nesaturovaná alternující cesta
Je taková alternující cesta, jejíž obě koncové hrany nepatří do párování
P.
