Лекция 10. Мосты, точки сочленения. Эйлеров цикл

• Обсуждение работы с неориентированными графами.  

• Запуск DFS на неориентированном графе.  

• Неориентированный граф обходит всю компоненту связности.  

• Пример неориентированного графа и его обход DFS.  

• Граф содержит множество ребер, соединяющих вершины.  

• Удаление ненужных ребер для упрощения графа.  

• Ребра в неориентированном графе соединяют предка с потомком.  

• Все ребра, не входящие в дерево, имеют такую структуру.  

• Исключение ребер, соединяющих предка с потомком, которые не входят в дерево.  

• В дереве DFS не бывает ребер, соединяющих предка с потомком, которые не входят в дерево.  

• Доказательство этого факта.  

• Важность понимания порядка посещения вершин для корректной работы DFS.  

• Мост - это ребро, удаление которого разбивает граф на несколько компонент связности.  

• Компоненты двусвязанности - это вершины, между которыми есть два непересекающихся пути.  

• Вершины связаны, если между ними есть два пути, не пересекающиеся по ребрам.  

• Доказательство транзитивности для компонент двусвязанности.  

• Пример с двумя путями из вершины У в вершину В и двумя путями из В в У.  

• Построение непересекающихся путей и доказательство их транзитивности.  

• Компоненты реберной двусвязанности делят вершины на классы эквивалентности.  

• Пример с левыми и правыми компонентами реберной двусвязанности.  

• Доказательство, что ребро соединяет две вершины в разных компонентах тогда и только тогда, когда оно является мостом.  

• Граф разбивается на компоненты реберной двусвязанности, связанные мостами.  

• Компоненты можно сконденсировать в дерево, оставив только мосты.  

• Преобразование графа в дерево позволяет решать множество задач быстрее.  

• План: запустить DFS и проверить ребра на наличие мостов.  

• Утверждение: все мосты лежат в дереве DFS.  

• Проверка ребер на наличие мостов: если удаление ребра разбивает дерево на два куска, то это ребро является мостом.  

• Проверка существования ребра, соединяющего потомка вершины с предком.  

• Использование тупого и не очень тупого метода для проверки.  

• Хранение максимума для проверки наличия элементов в множестве.  

• Поиск самого высокого ребра в поддереве вершины.  

• Использование отношения "выше" для сравнения вершин.  

• Проблемы с определением отношения "выше" на всех вершинах.  

• Сравнение вершин по глубине или времени входа.  

• Преимущества времени входа перед временем выхода.  

• Использование времени входа для сравнения вершин.  

• Подсчет самого высокого ребра в поддереве вершины.  

• Использование минимума для нахождения самого высокого ребра.  

• Учет ребер, ведущих из самой вершины.  

• Поиск компонентов двусвязанности реберной.  

• Использование стека для накопления вершин.  

• Исключение вершин из стека при обнаружении моста.  

• Определение точек счения и компонентов вершин до связанности.  

• Пример вершины, удаление которой увеличивает количество компонентов связанности.  

• Компоненты вершины двусвязности определяются как набор ребер.  

• Два ребра двусвязны, если между ними есть два пути, не пересекающиеся по вершинам.  

• Доказывается транзитивность отношения двусвязности.  

• Вершина является точкой зрения, если из нее выходят ребра разных компонент двусвязности.  

• Пример: ребра, принадлежащие одной компоненте, и ребра, принадлежащие другой компоненте.  

• Доказательство, что каждая вершина либо точка зрения, либо целиком принадлежит одной компоненте.  

• Вершины делятся на точки зрения и компоненты.  

• Декомпозиция графа: вершины - компоненты двусвязности, точки зрения - дополнительные вершины.  

• Соединение компонентов и точек зрения для получения дерева.  

• Удаление вершины из дерева приводит к его развалу на куски.  

• Если вершина не является точкой зрения, то из нее торчит ребро наверх.  

• Проверка наличия ребра наверх для определения точки зрения.  

• Удаление точек зрения и проверка оставшихся ребер.  

• Использование DFS для выделения компонентов.  

• Построение компонентов на основе ребер, которые отваливаются при удалении вершины.  

• Компоненты двусвязности можно строить на лету.  

• Возможность создания вершин и компонентов в DFS.  

• Завершение обсуждения точек зрения и переход к следующему пункту программы.  

• Эйлеров цикл проходит по всем ребрам графа ровно один раз.  

• В ориентированном графе эйлеров цикл существует, если у каждой вершины степени входа и выхода равны.  

• Можно сначала проверить, что граф эйлеров, а затем запустить алгоритм построения цикла, или наоборот.  

• Алгоритм использует обход в глубину с помеченными ребрами.  

• В каждую вершину заходят до тех пор, пока есть непомеченные ребра.  

• Если в вершине нет непомеченных ребер, алгоритм возвращается к предыдущей вершине.  

• Пример обхода графа с пометками ребер.  

• Если в вершине нет непомеченных ребер, алгоритм добавляет ребро в ответ.  

• Утверждается, что алгоритм строит эйлеров цикл, если граф эйлеров.  

• Если в вершине нет непомеченных ребер, это означает, что у всех остальных вершин их четное количество.  

• Если у одной вершины нечетное количество непомеченных ребер, это приводит к остановке алгоритма.  

• Если все вершины имеют четное количество непомеченных ребер, алгоритм продолжает работу.  

• Для реализации алгоритма нужна структура данных, которая быстро проверяет наличие непомеченных ребер.  

• В каждой вершине хранится множество непомеченных ребер, с операциями добавления и удаления ребер.  

• Ориентированный граф упрощает удаление ребер.  

• Каждое ребро находится в одном списке, что упрощает удаление.  

• Для удаления ребра нужно взять последнее ребро в списке и удалить его.  

• В неориентированном графе удаление ребер сложнее.  

• Можно хранить ссылки на ребра или их номера.  

• Удаление ребра требует проверки всех списков, чтобы убедиться, что оно удалено.  

• Пример с использованием DFS для удаления ребер.  

• Алгоритм добавляет ребра к ответу и удаляет их.  

• Пример показывает, как DFS работает с ориентированным графом.  

• Построение цикла в неориентированном графе.  

• Удаление ребер после построения цикла.  

• Алгоритм работает аналогично ориентированному графу.  

• Разреженные таблицы для быстрого вычисления функций.  

• Выбор отрезков для покрытия массива без пересечений.  

• Алгоритм разбивает массив на отрезки и вычисляет функцию на каждом отрезке.  

• Рассматривается задача нахождения минимального места разделения двух отрезков.  

• Предлагается использовать битовую запись для определения самого правого отличающегося символа.  

• Объясняется, как найти старший бит для каждого числа и использовать его для определения минимального места разделения.  

• Обсуждается, как использовать битовые операции для нахождения старшего бита.  

• Объясняется, что если числа вписываются в слово, то можно использовать битовые операции для поиска старшего бита.  

• Подчеркивается, что это можно сделать за логарифмическое время.  

• Объясняется, что дерево Феннека используется для работы с изменяющимися массивами.  

• Описывается, как дерево Феннека позволяет быстрее и эффективнее выполнять операции с массивами.  

• Приводится пример использования дерева Феннека для вычисления суммы элементов массива.  

• Описывается план создания массива для хранения сумм элементов.  

• Объясняется, как вычислять сумму элементов на префиксе.  

• Подчеркивается важность правильной функции для определения перекрывающихся отрезков.  

• Описывается алгоритм вычисления суммы элементов на префиксе.  

• Объясняется, как использовать битовые операции для определения перекрывающихся отрезков.  

• Подчеркивается, что алгоритм работает за логарифмическое время из-за замены единичек на нолики и последующего вычитания одного.  

• Для выполнения инкремента нужно найти все значения между двумя другими значениями.  

• Пример: найти значения, которые находятся между двумя другими значениями.  

• Пример: значения между двумя другими значениями выглядят как нолики и единички.  

• Для генерации значений нужно заменить все нолики на единички.  

• Для инкремента в точке нужно увеличить значение на икс.  

• Процесс: найти самый правый ноль, заменить его на единичку и перейти к следующему значению.  

• Метод работает быстрее и использует меньше памяти, чем дерево отрезков.  

• Подходит для задач, где требуется быстрое выполнение и экономия памяти.  

• Метод позволяет считать функции, но не обязательно для необратимых функций.  

• Можно построить дерево Фенвика из готового массива, что упрощает задачу.