Taneční

Algoritmus hledající nesaturované alternující cesty

Je speciálním případem obecného algoritmu, který funguje i pro grafy, které nejsou bipartitní.

Popis algoritmu

Krok 0

Najdeme libovolné (i prázdné) párování zadaného grafu.

Krok 1 (značkování)

Krok 1a Každému nesaturovanému vrcholu přiřadíme značku S:0. Všechny vrcholy jsou neprozkoumané.

Krok 1b Zvolíme libovolný neprozkoumaný vrchol i. Pokud má značku S:? jdeme na krok 1c, pokud má značku T:? jdeme na krok 1d. Jinak jdeme na krok 3.

Krok 1c Pro každou hranu i-j, která nepatří do párování P označíme neoznačený vrchol j značkou T:i.
Pokud je j označený značkou S, našli jsme nesaturovanou alternující cestu a jdeme na krok 2.
Pokud je j označený značkou T, tak ji ponecháme a jdeme na krok 1.

Krok 1d Pro jedinou hranu i-j, která patří do párování P označíme neoznačený vrchol j značkou S:i.
Pokud je j označený značkou T, našli jsme nesaturovanou alternující cestu a jdeme na krok 2.
Pokud je j označený značkou S, tak ji ponecháme a jdeme na krok 1.

Krok 2 (zvětšování)

Podél nalezené nesaturované alternující cesty prohodíme hrany, které do párování P patří a které do P nepatří. Párování zvětšíme, smažeme značky a jdeme na krok 1.

Krok 3

Žádná nesaturovaná alternující cesta neexistuje, nalezené párování je největší a algoritmus končí.

Zjednodušený popis algoritmu

Značkování slouží k nalezení nějaké alternující cesty.

Pro malé grafy stačí vždy "uvidět" nějakou alternující cestu a párování podél této alternující cesty zvětšit.