Семинар 10. Остовные деревья, сжатие компонент

Построение графа по запросам на достижимость и недостижимость (всесиб 2015). Проверка M достижимостей в (N,M)-графе за O(M N). Сжатие компонент сильной связности. Динамическое программирование в порядке топ. сорт. Использование битовых масок. Сокращение затрат памяти.

Найти мин. мн-во вершин, достижимых из любой вершины после удаления любого ребра. Мосты и компоненты двусвязности. Сжатие компонент, получение дерева. Мн-во висячих вершин = ответ. Количество ответов.

Задача о минимальном остовном дереве (МОД). Лес хороший, если дополняется до МОД. Разрез в графе. Лемма о разрезе (сохранение хорошести при добавлении ребра). Фундаментальные циклы графа относительно остовного дерева.

Алгоритм Прима. Множество посещённых вершин B. Добавляется мин. ребро в разрезе B | (V\B). Реализация по аналогии с алгоритмом Дейкстры, хранение мин. ребра для серых вершин. Время работы O(E log V).

Алгоритм Краскала. Храним лес, добавляем мин. ребро между деревьями. Сортировка рёбер, добавление по одному. Использование сист. неперес. мн-в для хранения компонент связности. Время работы O(E log V).

Убрали: Алгоритм Борувки. Фаза алгоритма, сжатие графа. Корректность: результат фазы - лес, сохранение хорошести (по лемме). Выполнение фазы за O(E), всего O(log V) фаз. Время работы O(E log V).