Срязващ връх и мост: определения и приложения.

Ефикасен алгоритъм за намиране на всички срязващи
върхове (Алгоритъм 25 и Алгоритъм 26).  Кратка
аргументация за коректността: Теорема 89, Теорема 90,
Теорема 91.  Кратко изследване на сложността.


Тегловни графи.  Покриващи дървета.  Тегло
на подграф.  Минимални покриващи дървета.

Сигурно ребро по отношение на множество от ребра.
Алгоритъм 27: Обща схема на алгоритъм за МПД.

Срез в граф.  Ребро, прекосяващо среза.
Кога срезът е съобразен с множество ребра.
Леко ребро по отношение на срез.

Теорема 93: МПД теоремата в засиления
вариант от CLR.  Доказателство на теоремата.

Алгоритъм на Prim за намиране на МПД.
Псевокод на алг. на Prim в изтънчения
вариант (Алгоритъм 28).  Базовият вариант на алгоритъма
на Prin не се иска!
Кратък анализ на коректността -- достатъчно
е да се посочи как се използва Теорема 93.
Не се очаква подробно доказателство с инвариант.
Анализ на сложността по време.

Алгоритъм на Kruskal (Алгоритъм 29): псевдокод и кратка
аргументация за коректността.  Достатъчно
е да се посочи как се използва Теорема 93.
Не се очаква подробно доказателство с инвариант.

Как се реализира алг. на Kruskal ефикасно:
примитиви FIND и UNION.

Union-Find структури данни.  
Реализация на разбиване чрез ориентирана гора.
Алгоритъм 30 (FIND).

Как се реализира UNION в константно време.
Проблеми със сложността на FIND, произтичащи
от произволен избор на нов корен в UNION.

Евристика UNION BY RANK.  Алгоритъм 31 (Union by rank,
където рангът е височината).  Теорема 98 за максималната
височина на дърво, което се получава от серия прилагания на
UNION BY RANK, където рангът е височината.  Какво
следва от това за сложността на алгоритъма
на Kruskal.