Занятие 1. Параллель B – Графы 1

Пересказ

Тезисы

• Времена входа (t_in) и выхода (t_out) вершин в DFS позволяют определить, что интервалы посещения вершин либо не пересекаются, либо вложены друг в друга. 9:48
• Топологическая сортировка — это упорядочивание вершин ориентированного графа таким образом, что все рёбра идут строго слева направо, и она возможна только для ориентированных ациклических графов (ДАГ). 13:04
• Корректную топологическую сортировку ДАГ можно получить, отсортировав все вершины в порядке убывания их времен выхода (t_out), полученных при обходе DFS. 25:06
• Конденсация графа — это процесс сжатия каждой КСС в одну вершину, в результате чего получается новый граф, который всегда является ДАГ. 51:18
• Компоненты сильной связности (КСС) — это максимальные подмножества вершин, в которых любая пара вершин взаимно достижима, и они сохраняются при обращении всех рёбер графа. 74:10
• Алгоритм поиска КСС (например, Косарайю) включает два прохода DFS: первый для вычисления t_out всех вершин, а второй — на обращенном графе, начиная с непосещенных вершин в порядке убывания t_out. 91:24
• Динамическое программирование (ДП) на деревьях часто решается с помощью DFS, например, для нахождения максимальной глубины поддерева или диаметра дерева. 114:30
• Для задач ДП на деревьях, таких как поиск максимального независимого множества, удобно использовать несколько состояний ДП для каждой вершины (например, вершина включена или исключена). 130:38
• При решении задач на ДАГ, таких как подсчет количества путей или суммы длин путей, можно использовать ДП, обрабатывая вершины в порядке, обратном топологической сортировке, чтобы гарантировать, что значения для "дальнейших" вершин уже посчитаны. 146:10
• Топологическая сортировка ДАГ предоставляет естественный порядок обработки вершин для решения задач динамического программирования, таких как нахождение самого длинного пути. 225:22