Advanced Graphs

В тази секция ще наблегнем на няколко от по-сложните алгоритми в графи - намиране на оптимално двойкосъчетание ("matching"), потоци ("maximum flows"), удовлетворяване на булев израз ("2-SAT"), така наречения Унгарски Алгоритъм, който се справя със задачата за разпределението ("assignment problem"), и дори ще зачекнем максимални потоци с минимална цена ("Min-cost Max-flow"). Идеята (а и имплементацията, в някои случаи) на тези алгоритми не е тривиална, и всъщност броят програмисти, които могат да ги напишат без помощта на интернет или книга е много малък (под 1%). Както ще видите, с тях обаче могат да се зададат доста интересни задачи, в които самото досещане, че може да се ползва някой от тези алгоритми е относително сложно.

Теми, които биха ви помогнали за тази секция, са Оптимално двойкосъчетание, Максимални потоци, Удовлетворяване на булеви изрази, Унгарски алгоритъм, и Потоци с минимална цена.

Голяма част от задачите в секцията се решават с мачинг или поток, но има и няколко, които са с някои от другите.