Primjer okretanja bridova kod sparivanja

Okretanjem bridova poboljšavamo rješenje

• Na početku, sve veze su okrenute iz skupa prema skupu . Dakle, čvorovi sive boje dio su skupa .

• Tražimo put koji počinje u skupu , i završava u skupu . Jedan taka put je . Na tom putu okrećemo sve bridove.

• Sljedeći takav put je .

• Okretanjem svih bridova na njemu, dobivamo sljedeće sparivanje:

• Vidljivo je da ako postoji put koji počinje u skupu i završava u skupu u vrhu iz kojeg nije moguće doći nazad (u već nesparenom vrhu), okretanjem bridova na tom putu povećavamo rješenje za 1.

© 2013. Anton Grbin

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License