Информатика · объяснение и практика
Как порядок без входящих рёбер решает зависимости в ациклическом графе
Разберите зависимости по входящим рёбрам: выберите доступный шаг, обновите счётчики и отличите допустимый порядок от расписания с длительностями.

В теме Графы и маршруты · Учебная карта
Главная мысль
Для зависимостей «сначала А, затем Б» топологический порядок ставит А раньше Б. В ориентированном графе без циклов такой порядок существует. Можно последовательно выбирать вершины, у которых не осталось входящих рёбер из ещё не обработанной части.
Начните с задачи, которую уже можно выполнить
В проекте стенгазеты сначала собирают фотографии и пишут подписи. Оба результата нужны для макета, а готовый макет — для печати. Обозначим эти действия Ф, П, М и Т. Рёбра Ф→М, П→М, М→Т записывают обязательную последовательность. Между фотографиями и подписями ребра нет: правило не требует выполнять их в определённом взаимном порядке.
Посчитаем входящие рёбра: у Ф и П их ноль, у М два, у Т одно. Первые две задачи доступны сразу. Выбирая Ф, убираем её исходящее ребро и уменьшаем счётчик М до одного. Макет ещё недоступен: выполнена только одна из двух предпосылок. В очередь добавляют вершину именно при достижении нуля, а не после любого уменьшения счётчика.
Проверьте все рёбра, а не сходство списка
После обработки П счётчик М обнуляется. Затем можно выполнить М и Т. Получается Ф, П, М, Т. Порядок П, Ф, М, Т тоже корректен. Неединственность отражает отсутствие ограничения между двумя начальными действиями; она не свидетельствует об ошибке алгоритма. Если требуется алфавитный выбор среди доступных вершин, это дополнительное правило разрешения равенства.
Для проверки готового списка сопоставьте каждой вершине её позицию. Для каждого ребра начало должно стоять раньше конца. Например, список Ф, М, П, Т нарушает зависимость П→М, хотя содержит все четыре названия без повторений. Одного совпадения наборов вершин недостаточно. Отдельно проверяют, что никакая задача не пропущена и не записана дважды.
Пример
Даны зависимости К→Н и Л→Н. Допустим ли порядок Л, К, Н?
Да. Обе предпосылки К и Л стоят раньше Н. Между К и Л условия не установлено, поэтому их взаимный порядок свободен. Список Н, К, Л нарушил бы сразу два ребра.
Пустая очередь иногда означает конфликт
Если очередь опустела раньше обработки всех вершин, в оставшейся части есть направленный цикл. Каждая ещё не выполненная задача ждёт другую, поэтому просто выбрать «самую важную» нельзя без нарушения условий. Это отличается от обычного окончания работы: при успешном завершении число обработанных вершин равно общему числу. Изолированная вершина тоже входит в список и доступна с начала.
При списках смежности каждое ребро учитывается при подсчёте и затем при удалении, что даёт время O(V+E) для варианта с обычной очередью. Топологический порядок сам по себе не вычисляет календарные сроки. Для параллельного расписания нужны длительности, исполнители и правило запуска; для поиска кратчайшего пути нужна другая цель. Сначала зафиксируйте смысл стрелки, затем выбирайте алгоритм.
От чтения к действию
А теперь — вы
Частые вопросы
Почему могут получиться разные правильные списки?
Некоторые задачи не связаны требованиями порядка. Их можно переставлять, если каждое ребро по-прежнему направлено от более ранней позиции к более поздней.
Изолированную вершину можно не записывать?
Если требуется порядок всех вершин, её включают. У неё нет предпосылок, поэтому она доступна сразу.
Углублённый разбор
Свидетель единственности топологического порядка
Найденный топологический список может быть одним из многих. Единственность проверяется локально по доступным вершинам либо по рёбрам между соседями уже найденного списка, без перечисления всех вариантов.
Перед началом: Топологический порядок; Алгоритм Кана.
Два одновременных выбора дают два разных результата
В алгоритме Кана доступны вершины с нулевой текущей входящей степенью. Если в какой-то момент доступны разные u и v, между ними нет ребра: иначе его конец имел бы незавершённого предшественника. Можно выполнить сначала u, затем v либо наоборот, после чего одинаково продолжить обработку оставшегося DAG. Поэтому порядок не единственен.
Обратно, если на каждом шаге доступна ровно одна вершина, первый элемент вынужден, затем вынужден второй и так далее. По индукции любой допустимый порядок совпадает с построенным. Это критерий для ациклического графа; если доступных вершин нет до завершения, ситуация означает цикл, а не единственный порядок.
Соседние элементы дают короткий сертификат
Пусть v₁,…,vₙ уже является корректным топологическим порядком. Он единственен тогда и только тогда, когда для каждого i имеется ребро vᵢ→vᵢ₊₁. При наличии всех таких рёбер они образуют направленный путь через все вершины и заставляют любой допустимый список сохранить всю цепочку.
Если ребра между соседями нет, эти два элемента можно поменять местами. Другие вершины остаются по ту же сторону обоих элементов, поэтому все остальные зависимости сохраняются. Направленного пути длинее одного между ними тоже быть не может: его промежуточная вершина должна была бы стоять между соседними позициями. Значит отсутствие ребра действительно даёт второй порядок.
Правило выбора не доказывает вынужденность
Алфавитный выбор, минимальная метка или стабильная очередь делают конкретную реализацию детерминированной. Но детерминированный вывод не означает, что входные зависимости допускают только его. Свойство графа проверяется до применения искусственного правила разрешения равенства. Это важно, когда список используется как доказательство обязательной последовательности задач.
Для конечной проверки достаточно сначала подтвердить корректность списка по всем рёбрам, затем проверить соседние пары. Без первого шага наличие части последовательных рёбер не спасает неверный список. При хранении соседей во множествах проверки выполняются быстро; точная сложность зависит от выбранного представления и стоимости поиска ребра.
Снять неоднозначность одной зависимостью
Условие. Граф имеет A→B,A→C,B→D,C→D. Исследуйте единственность порядка, затем добавьте B→C.
- В начале доступна только A. После её удаления одновременно доступны B и C, поэтому исходный порядок не единственен.
- Два явных допустимых списка: A,B,C,D и A,C,B,D. Они различаются ровно перестановкой независимых B,C.
- После добавления B→C вершина C ждёт B. Все шаги становятся вынужденными: A, затем B, затем C, затем D.
- Соседние рёбра A→B,B→C,C→D образуют сертификат единственности нового списка. Каждая исходная зависимость также направлена вперёд.
Ответ. До добавления два порядка; после B→C единственный A,B,C,D.
Проверка. Перебор всех 24 перестановок четырёх вершин оставляет соответственно 2 и 1 допустимый список. Число проходящих проверку не зависит от порядка перечисления соседей.
Где легко ошибиться. Детерминированная очередь выдаёт один воспроизводимый список даже при множестве допустимых порядков. Не путайте свойство реализации с единственностью, заданной самими рёбрами.
Проверьте понимание
Вопросы к этой главе
Одна изолированная вершина разрушает единственность?
Если граф содержит и другие вершины, обычно да: изолированную можно вставить в разные места. Для графа из одной вершины единственный порядок существует и соседних пар нет.
Нужно искать произвольный гамильтонов путь?
Нет. В DAG достаточно взять уже найденный топологический порядок и проверить рёбра между соседями. Если единственный порядок существует, его последовательные рёбра обязаны присутствовать.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- James Aspnes, Yale: TopologicalSort
Авторские университетские заметки: вебом проверены определение порядка DAG и линейная стоимость обычной сортировки. Критерий единственности и обновления при добавлении ребра доказаны в данной главе отдельно.
Равномерная генерация топологического порядка через числа продолжений
Случайный выбор одной из доступных задач обычно не даёт равномерного распределения полных порядков. Чтобы каждый допустимый список имел одинаковую вероятность, выбор взвешивают числом его будущих продолжений.
Перед началом: Линейное расширение; Условная вероятность.
Равные первые шансы могут вести в ветви разного размера
Пусть F(S) — число допустимых завершений при оставшемся наборе задач S. Для каждой доступной первой v существует F(S без v) продолжений. Эти ветви не пересекаются и покрывают все завершения, поэтому их размеры суммируются в F(S). Для равномерного полного результата вероятность выбрать v должна равняться F(S без v)/F(S).
Равномерный выбор среди доступных вершин считает одинаковыми ветви, а не отдельные листья дерева решений. Если одна ветвь содержит два полных списка, другая один, одинаковые шансы первого шага дадут списку второй ветви вдвое большую вероятность. Такой перекос возникает даже у трёх задач и не связан с качеством генератора случайных чисел.
Вероятности телескопически сокращаются
Вдоль конкретного полного порядка перемножаются отношения F(S_next)/F(S_current). Числитель каждого шага совпадает со знаменателем следующего. В конце F(∅)=1, поэтому вероятность любого листа равна 1/F(V). Это доказывает точную равномерность сразу для всех допустимых порядков, а не только для одной удачной пары.
Практически можно выбрать целый билет из диапазона 0,…,F(S)−1 и разбить его на блоки длин F(S без v). Так избегают округления дробных вероятностей. Сам генератор целого билета также должен быть равномерным; простое взятие остатка от неравномерного или неподходящего диапазона способно вернуть смещение.
Сложность подсчёта не исчезает при переходе к выборке
Точный F можно хранить для достижимых остаточных наборов, но число таких состояний в худшем случае экспоненциально. Поэтому описанная схема является точным методом для посильных конечных DAG, а не обещанием дешёвой выборки из любого большого графа. Приближённые методы требуют отдельного анализа расстояния до равномерного распределения.
Если зависимость содержит цикл, F(V)=0 и выбирать билет невозможно. Пустой граф задач имеет ровно один пустой порядок, а не ноль способов. Явное разделение этих случаев нужно и в рекурсии, и в итоговом статусе. Сравнение точных вероятностей с прямым перечислением маленького графа служит независимой проверкой sampler-правила.
Три порядка с разными шансами первого шага
Условие. Есть задачи A,B,C и единственная зависимость A→C. Сравните равный выбор доступной вершины с выбором по числу завершений.
- Полные допустимые порядки равны ABC,ACB,BAC. Их всего три.
- Если первой выбрана A, остаются два порядка B,C либо C,B. Если первой B, остаётся только A,C.
- При равных шансах A,B получаем вероятности 1/4,1/4,1/2. Они неравномерны.
- Нужны вероятности первого выбора P(A)=2/3,P(B)=1/3. После A два завершения выбираются поровну, и каждый полный порядок получает 1/3.
Ответ. Равномерный sampler выбирает A первым с вероятностью 2/3, B с 1/3.
Проверка. Три итоговые вероятности равны(2/3)(1/2),(2/3)(1/2),1/3. Их сумма единица; прямой список из трёх порядков подтверждает целевые веса.
Где легко ошибиться. Одинаковая вероятность каждого доступного шага не означает одинаковую вероятность полного результата. Нужно учитывать размеры поддеревьев возможных завершений.
Проверьте понимание
Вопросы к этой главе
Нужно сначала перечислить все полные списки?
Нет. Достаточно точных чисел завершений для остаточных состояний. Однако вычисление этих чисел само по себе может потребовать много состояний и больших целых чисел.
Можно брать приблизительные числа продолжений?
Можно построить приближённую схему, но точная телескопическая гарантия равномерности исчезнет. Ошибки весов способны накапливаться, поэтому нужен отдельный контроль распределения.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Lehman, Leighton, Meyer: Mathematics for Computer Science
Первичный учебник MIT: вебом проверены частичные порядки и линейные расширения. Точный sampler через числа продолжений и телескопическое доказательство равномерности выведены отдельно; современные MCMC-методы не используются.
Добавление зависимости и проверка нового цикла
Одна новая зависимость может создать цикл или лишь сделать прежний порядок неудобным. Проверка обратного пути в старом графе точно различает эти случаи и даёт явный сертификат отказа.
Перед началом: DAG; Достижимость.
Новый цикл обязан использовать новое ребро
Пусть исходный ориентированный граф ацикличен и добавляется u→v. Цикл возникает тогда и только тогда, когда в старом графе имеется путь v→u. Достаточность очевидна после замыкания этого пути новым ребром. Для необходимости удаляют новое ребро из возникшего цикла: остальная его часть уже была старым путём от v к u.
Петля u=v создаёт цикл сразу, если пустой путь к себе включён в достижимость. Повторная копия уже существующего ребра не создаёт новый цикл в DAG. Для практического отчёта полезно вернуть не только логический ответ, но и найденный путь v→u: вместе с новым ребром он становится проверяемой последовательностью зависимостей.
Старые позиции позволяют сократить поиск
Если известен топологический порядок π и π(u)<π(v), новый переход уже направлен вперёд и прежний список остаётся корректным. Если π(u)>π(v), цикл ещё не доказан: обратное направление относительно одного выбранного списка может соединять раньше независимые вершины. Нужно проверить достижимость.
Путь v→u в старом DAG может проходить только через вершины с позициями между π(v) и π(u), поскольку каждое старое ребро увеличивает позицию. Поэтому поиск можно ограничить этим диапазоном. Это безопасное сокращение области, а не гарантия постоянного времени: между границами всё ещё может находиться значительная часть графа.
Отсутствие цикла не сохраняет сам список автоматически
Если обратного пути нет, обновлённый граф остаётся DAG и некоторый новый порядок существует. Но прежний список с π(u)>π(v) нарушает добавленное ребро. Его нужно перестроить либо корректно обновить с учётом всех зависимостей. Произвольный обмен только двух концов может сломать связи с промежуточными вершинами.
При серии обновлений проверка каждого следующего ребра относится к уже обновлённому графу. Использование старого снимка достижимости может пропустить цикл, собранный несколькими новыми зависимостями. Явный инвариант «текущий граф DAG, текущий список корректен» отделяет проверку нового условия от восстановления структуры данных.
Цикл или только новый порядок
Условие. Исходные рёбра A→C,B→C,C→D, порядок A,B,C,D. По отдельности исследуйте добавление D→B и B→A.
- Для D→B ищем старый путь B→D. Он существует: B,C,D. Новое ребро замыкает цикл B,C,D,B.
- Для B→A ищем старый путь A→B. Из A можно попасть лишь в C,D, поэтому такого пути нет.
- Граф с B→A остаётся ацикличным, хотя старый список A,B,C,D уже нарушает новую зависимость.
- Новый корректный список B,A,C,D сохраняет B→A,A→C,B→C,C→D. Значит обратное по старым позициям ребро не всегда создаёт цикл.
Ответ. D→B создаёт цикл; B→A требует смены порядка, но цикла не создаёт.
Проверка. В первом случае предъявлены все три ребра цикла. Во втором прямой проверкой позиций нового списка подтверждены все четыре ограничения.
Где легко ошибиться. Ребро назад относительно старого топологического списка не равносильно циклу. Точный критерий использует старый путь из нового конца в новое начало.
Проверьте понимание
Вопросы к этой главе
Можно просто пересортировать граф?
Да, полный повтор алгоритма является корректным способом проверки. Инкрементальный критерий полезен, когда хочется использовать уже известный порядок и ограничить поиск затронутой областью.
Почему путь проверяется до добавления ребра?
Так получаем точный старый фрагмент потенциального цикла. После добавления тоже можно искать цикл, но нужно аккуратно отличать новое ребро и не выдавать его повторное использование за независимый путь.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- James Aspnes, Yale: TopologicalSort
Авторские университетские заметки: вебом проверены определение порядка DAG и линейная стоимость обычной сортировки. Критерий единственности и обновления при добавлении ребра доказаны в данной главе отдельно.
Минимальное покрытие DAG цепями и наибольшая антицепь
Топологический порядок размещает элементы в одну линейную последовательность, но не делает их попарно сравнимыми. Теорема Дилуорса связывает другую задачу: минимальное разбиение частичного порядка на цепи равно размеру наибольшей антицепи. Паросочетание строит покрытие, а антицепь независимо доказывает его оптимальность.
Перед началом: Частичный порядок и достижимость в DAG; Двудольное паросочетание.
Цепь использует сравнимость, а не соседство исходных дуг
В частичном порядке цепь — множество попарно сравнимых элементов, антицепь — множество попарно несравнимых. Для DAG используем строгий порядок достижимости. Соседние элементы цепи поэтому могут соединяться путём, а не одной исходной дугой. Для соответствующей редукции нужны все пары строгой достижимости, то есть транзитивное замыкание.
Каждая цепь содержит не больше одного элемента любой антицепи. Значит, антицепь размера k требует хотя бы k цепей в любом покрытии. Это простое нижнее свидетельство не зависит от алгоритма поиска покрытия. Сама теорема Дилуорса утверждает достижимость такой нижней границы для всякого конечного частичного порядка.
Две копии множества превращают сшивание цепей в matching
Создадим левую и правую копии каждого элемента. Добавим ребро x_L→y_R, если x<y. Выбранное паросочетание задаёт для каждого элемента не больше одного следующего и одного предыдущего элемента цепи. Цикл невозможен из-за строгого порядка, поэтому получаются непересекающиеся цепи, покрывающие все вершины.
Каждое ребро паросочетания уменьшает число отдельных цепей на единицу. При n элементах результат содержит n−|M| цепей. Обратно, последовательные пары любого разбиения на цепи образуют такое паросочетание размера n−число цепей. Поэтому максимальное matching даёт минимальное число цепей. Теорема Дилуорса связывает этот минимум с максимальной антицепью.
Двойственное свидетельство проверяется без доверия к поиску
В малом случае достаточно предъявить k цепей, покрывающих элементы без пропусков, и антицепь размера k. Покрытие доказывает верхнюю границу, антицепь — нижнюю, и они совпадают. Не требуется доказывать оптимальность паросочетания только отсутствием очевидного локального улучшения.
Для больших экземпляров антицепь извлекают через двойственные объекты максимального двудольного matching и минимального вершинного покрытия. Но сравнимость нужно сохранять в исходном частичном порядке. Если ошибочно использовать только соседство в диаграмме Хассе, полученная задача может отличаться от покрытия произвольными цепями достижимости.
Три несравнимые середины задают ширину
Условие. Порядок на a,b,c,d,e,f задан отношениями a<c,a<d,b<d,b<e,c<f,d<f,e<f и всеми их транзитивными следствиями. Найдите минимум цепей и подтвердите его антицепью.
- Транзитивное замыкание дополнительно содержит a<f и b<f. В частности, порядок не сводится только к семи записанным соседним отношениям.
- В двудольной редукции выберем matching a_L→c_R,c_L→f_R,b_L→d_R. Левые и правые концы отдельно не повторяются, хотя c участвует в обеих разных копиях.
- Получаем цепи a<c<f, b<d и отдельный элемент e. Они попарно не пересекаются и покрывают все шесть элементов, поэтому трёх цепей достаточно.
- Элементы c,d,e попарно несравнимы. Их антицепь размера три требует как минимум три цепи в любом покрытии.
- Верхняя и нижняя границы совпали. Matching размера три максимально, минимальное число цепей равно 6−3=3, ширина порядка тоже равна трём.
Ответ. Оптимум равен 3. Покрытие: {a,c,f}, {b,d}, {e}; максимальная антицепь: {c,d,e}.
Проверка. Перебор всех подмножеств проверяет максимальную антицепь, а независимый перебор двудольных matching подтверждает размер три. Явные цепи удостоверяют допустимость покрытия.
Где легко ошибиться. Не путайте линейное расширение порядка с одной цепью. В топологической последовательности несравнимые элементы стоят в каком-то порядке, но от этого не становятся сравнимыми.
Проверьте понимание
Вопросы к этой главе
Почему c можно использовать в двух рёбрах matching?
Это разные вершины двудольного графа: c_R принимает предыдущее звено, c_L задаёт следующее. Ограничение matching действует отдельно на каждую копию.
Зачем нужна антицепь, если покрытие уже найдено?
Покрытие показывает только достижимость некоторого числа цепей. Антицепь того же размера доказывает, что меньшее число невозможно, и делает оптимальность независимо проверяемой.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- V. K. Garg: bipartite matching and Dilworth duality
Прочитаны разделы о теореме Дилуорса и strict split reduction с рёбрами x<y. Конкретный шеститочечный порядок, matching и антицепь рассчитаны независимо; результат относится к цепям порядка достижимости, а не только к путям по исходным дугам.
Вставка дуги: локальное исправление топологического порядка
Добавление зависимости не всегда требует полной топологической сортировки. Если новая дуга направлена вперёд в текущем порядке, он уже пригоден. Для обратной дуги достаточно исследовать ограниченный интервал: достижимые от её конца вершины и предшественники её начала. Пересечение даёт цикл, отсутствие пересечения позволяет исправить порядок, сохранив внутренний порядок каждой группы.
Перед началом: Проверка топологического порядка по позициям; Прямая и обратная достижимость.
Опасный путь целиком лежит между концами новой дуги
Конечный DAG с известным топологическим порядком; добавляется одна дуга, вершины не меняются, циклическая вставка отклоняется.
Пусть добавляется u→v. Если pos(u)<pos(v), все прежние дуги и новая согласованы с порядком, поэтому цикл возникнуть не может. Если pos(u)>pos(v), цикл возникает ровно тогда, когда старый граф уже содержит путь v→u. Петля u=v сразу даёт конфликт и не требует обычного поиска.
Старый путь идёт только вперёд в старом порядке. Поэтому для проверки v→u достаточно вершин интервала I от v до u включительно. Выход за его правую границу уже не позволит вернуться к u; вершины левее v на таком пути также невозможны. Это ограничение корректности, а не эвристическое обрезание произвольного обхода.
Два множества показывают конфликт или безопасные группы
В старом подграфе I находим F — достижимые из v, включая v, и B — вершины, из которых достижима u, включая u. Для B обходим обратные дуги. Если F∩B непусто, конкатенация путей v→x→u с новой u→v является свидетельством цикла. Предшественники поиска позволяют вернуть его явную запись.
Если пересечения нет, обозначим остальные вершины интервала через M. Заменим порядок внутри I на B,M,F, сохранив прежний относительный порядок внутри каждой группы. Дуга u→v теперь идёт из первой группы в последнюю. Все вершины за пределами I сохраняют позиции относительно целого интервала.
Почему перестановка не ломает старые зависимости
Опасными были бы старые дуги из M в B или из F в M: первая сделала бы начало предшественником u, вторая — конец достижимым из v, вопреки принадлежности M. Дуга из F в B дала бы старый путь v→u и пересечение, которое уже проверено. Остальные межгрупповые дуги направлены вперёд, а внутри групп порядок сохраняется.
Рассматриваемый простой вариант может просмотреть весь интервал и все его дуги; худший случай одного обновления остаётся O(n+m). Он не наследует автоматически более сильные амортизированные оценки специальных структур динамической сортировки. Его польза — локальность обычного случая и короткое проверяемое доказательство перестановки.
Одна вставка переставляет блок, вторая замыкает путь
Условие. Исходный порядок a,b,c,d,e,f,g,h. Старые дуги a→d,b→e,d→f,c→g,e→h. Сначала добавьте g→b, затем попытайтесь добавить h→c. Для безопасной перестановки используйте стабильный порядок групп B,M,F.
- Для g→b опасный интервал равен b,c,d,e,f,g. Прямой поиск из b внутри него даёт F={b,e}; h находится за правой границей. Обратный поиск к g даёт B={c,g}.
- Пересечения нет, M={d,f}. Стабильная перестановка интервала B,M,F даёт c,g,d,f,b,e. Полный новый порядок: a,c,g,d,f,b,e,h.
- Проверяем все старые дуги и новую g→b: каждая идёт вперёд. В частности, сохранены d→f, b→e и e→h; перемещение не ограничилось механическим обменом двух концов.
- Для следующей вставки h→c уже существует путь c→g→b→e→h. Он вместе с новой дугой замыкает цикл. Вторую вставку отклоняем, сохраняя граф и порядок после первого шага.
Ответ. Первая вставка допустима, порядок a,c,g,d,f,b,e,h. Вторая создаёт цикл c→g→b→e→h→c.
Проверка. Независимая проверка позиции каждого ребра подтверждает первую перестановку. Полная сортировка Кана обрабатывает все восемь вершин после g→b, но не может обработать весь граф после h→c; явный пятивершинный цикл объясняет отказ.
Где легко ошибиться. Не переставляйте только u и v. Их предшественники и потомки внутри интервала могут сохранить старое взаимное ограничение, которое такой обмен нарушит.
Проверьте понимание
Вопросы к этой главе
Почему h не включается в F при первой вставке, хотя достижима из b?
Проверяется только интервал до g. Вершина h стоит правее него и не может вернуться по старым прямым дугам к g, поэтому для конфликта и перестановки внутри интервала она не нужна.
Удаление дуги тоже требует исправления порядка?
Само удаление не нарушает уже выполненных неравенств позиций: ограничений становится меньше. Это отличается от добавления обратной дуги; поддержание других характеристик графа может потребовать отдельного обновления.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- Haeupler, Sen, Tarjan — Incremental Topological Ordering, §2
Двунаправленный поиск при нарушающей порядок вставке и цикл через встречу поисков. Здесь используется самостоятельно доказанный простой вариант с полными множествами интервала, без специальных амортизированных оценок статьи.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как состояние вершины помогает обнаружить цикл ориентированного графа
Ищем цикл ориентированного графа по состояниям вершин, отличаем активную ветвь от уже законченной и не принимаем любое повторное посещение за доказательство цикла.
Открыть темуПочему поиск в ширину находит кратчайший путь в невзвешенном графе
Находим минимальное число рёбер от стартовой вершины поиском в ширину, сохраняем предшественников для маршрута и объясняем, почему взвешенный путь требует другой модели.
Открыть тему