Информатика · объяснение и практика

Как состояние вершины помогает обнаружить цикл ориентированного графа

Ищем цикл ориентированного графа по состояниям вершин, отличаем активную ветвь от уже законченной и не принимаем любое повторное посещение за доказательство цикла.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

Главная мысль

В DFS ориентированного графа полезны состояния: не посещена, активна в текущей ветви, обработана. Ребро к активной вершине замыкает цикл; ребро к уже законченной вершине само по себе цикла не доказывает.

Почему одного visited недостаточно

Пусть рёбра А→Б, А→В, В→Б. Если сначала полностью обработать Б, затем войти в В, ребро В→Б ведёт к уже посещённой вершине. Но цикла нет: из Б не задан путь назад к В или А. Проверка «любой сосед уже visited» ошибочно объявила бы цикл в этом ациклическом графе.

Нужно хранить не только факт открытия, но и факт завершения ветви. Активная вершина находится в текущем стеке пути от старта DFS. Законченная уже покинула его после обработки всех исходящих рёбер. Эти состояния отвечают на разные вопросы, и объединение их одним цветом теряет информацию, необходимую для распознавания обратного ребра.

Как обратное ребро замыкает маршрут

Рассмотрим А→Б, Б→В, В→А. При входе А, затем Б, затем В все три активны. Ребро В→А возвращает к предку текущей ветви. Путь А→Б→В уже существует по рёбрам DFS, а последнее ребро замыкает его в цикл. Самопетля А→А также является циклом и обнаруживается тем же условием активности.

После обработки всех соседей вершину отмечают законченной. Если забыть это действие, она навсегда останется активной и будет порождать ложные циклы в поздних ветвях. Если закончить её слишком рано, до обхода потомков, можно пропустить настоящий цикл. Момент смены состояния является частью алгоритма, а не украшением визуализации.

Пример

В графе А→Б, Б→В, А→В есть ли цикл?

Нет. Есть два пути из А к В, но нет направленного пути обратно. Повторная достижимость одной вершины не равна циклу.

Как охватить весь граф и сохранить модель

Один запуск DFS из одной вершины проверяет только достижимую часть. Чтобы найти цикл где угодно, начинают обход из каждой ещё не посещённой вершины. Пустой граф без рёбер ацикличен. Для больших глубин рекурсивная реализация может превысить стек, поэтому применяют явный стек, сохраняя фазы входа и выхода.

В неориентированном графе правило требует отдельного обращения с ребром к родителю: оно присутствует в обоих направлениях представления, но не является самостоятельным циклом. Эта статья рассматривает именно ориентированные рёбра, где такой автоматической обратной записи нет. Перед применением критерия нужно проверить тип графа, наличие петель и договорённость о повторяющихся рёбрах. Алгоритм определяется моделью данных, а не только набором слов visited и stack.

От чтения к действию

А теперь — вы

В ориентированном DFS ребро ведёт к активному предку текущей ветви. Что это показывает?

Частые вопросы

Ребро к любой посещённой вершине доказывает цикл?

Нет. В ориентированном DFS существенна активность вершины в текущем стеке, а не только факт посещения.

Достаточно проверить одну компоненту?

Только если известна достижимость всего графа из старта. Иначе нужны запуски из остальных непосещённых вершин.

Углублённый разбор

Бесконечное принимаемое слово и лассо автомата Бюхи

Автомат Бюхи принимает бесконечный прогон, если финальные состояния посещаются бесконечно часто. Поэтому один достижимый финал не даёт положительного ответа. Непустоту языка удостоверяет конечное лассо: путь к принимающему циклу и ненулевой замкнутый обход, который можно повторять.

Перед началом: Сильно связная компонента; Бесконечная последовательность.

Принимающий финал не является концом бесконечного слова

НКА Бюхи имеет конечное множество состояний, буквенные переходы, начальное состояние и множество F. Входное слово содержит бесконечно много букв. Оно принимается, если существует бесконечный прогон, посещающий F бесконечно часто. Принимающая вершина с тупиком не даёт такого прогона: достигнуть её конечным словом и остановиться недостаточно.

Если принимающий прогон существует, хотя бы одно финальное состояние q встречается в нём бесконечно много раз, поскольку состояний конечно. Возьмём конечный префикс до q и ненулевой участок между двумя его посещениями. Их метки u и v задают бесконечное слово uv^ω, причём v непусто. Повторение найденного обхода снова посещает q и даёт принимающее лассо.

SCC нужна вместе с настоящим циклом

В обратную сторону достижимый непустой замкнутый обход через финальное состояние сразу даёт непустой язык. Такой обход существует в достижимой SCC с финалом, если компонента имеет хотя бы две вершины либо является одной вершиной с петлёй. Одиночная SCC без петли не подходит, хотя по соглашению нулевого пути вершина достижима сама из себя.

Поэтому проверка состоит из достижимости, SCC и проверки цикличности нужной компоненты. Она линейна по графу автомата. Не требуется перебирать все бесконечные слова: конечный граф гарантирует существование периодического свидетеля при непустоте. Это утверждение о наличии хотя бы одного подходящего слова, а не о том, что каждое принимаемое слово обязано быть в конечном счёте периодическим.

Префикс и цикл проверяются разными условиями

Префикс может не посещать финалы вообще, поскольку конечное число ранних посещений не влияет на требование бесконечности. Повторяемый участок обязан содержать финал, иначе после префикса принятие исчезнет. Для недетерминированного автомата достаточно одного такого прогона; другие ветви могут тупиковать. В проверочном свидетельстве нужно сохранить последовательность состояний и буквы цикла, чтобы отдельно удостоверить каждый переход и непустую длину v.

Принимающий тупик и принимающее лассо

Условие. Начальное состояние 0; финалы{1,3}. Переходы:0→a1,1→b2,2→c1,0→d3. Других переходов нет. Найдите принимаемое бесконечное слово и объясните роль состояния 3.

  1. Компоненты графа: {0},{1,2},{3}. Все достижимы, но{3} не имеет петли и потому не поддерживает бесконечное продолжение.
  2. Путь 0→a1 даёт префикс u=a. Из1 есть замкнутый обход 1→b2→c1 с непустой меткой v=bc.
  3. Слово a(bc)^ω имеет прогон 0,1,2,1,2,1,… и посещает финальное 1 бесконечно часто, поэтому принимается.
  4. После буквы d автомат попадает в финальное 3, но следующую букву прочитать не может. Любое бесконечное слово с началом d отвергается, несмотря на одно раннее финальное посещение.

Ответ. Принимаемое лассо a(bc)^ω; достижимый финал 3 сам по себе не свидетельствует непустоту.

Проверка. Прямой анализ детерминированного продолжения после a даёт бесконечное чередование b,c. Отдельный перебор непустых замкнутых обходов через финалы находит цикл 1–2–1 и не находит ни одного через 3.

Где легко ошибиться. Не принимайте любую достижимую финальную SCC за положительный ответ без проверки ненулевого цикла. Одиночная вершина с нулевым путём не заменяет бесконечный прогон.

Проверьте понимание

Какое бесконечное слово принимается указанным автоматом?

Вопросы к этой главе

Может ли цикл содержать не принимающие вершины?

Да. Требуется бесконечно часто посещать хотя бы один финал, а не оставаться в F на каждом шаге. В нашем цикле 2 не финально, но1 возвращается через каждые две буквы.

Все ли принимаемые слова должны иметь форму uv^ω?

Нет. Теорема говорит, что при непустом языке существует хотя бы одно такое слово-свидетель. Язык может также содержать непериодические бесконечные слова, в зависимости от переходов автомата.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • CMU15-414: Emptiness Checking, LTL Büchi Automata

    Прочитаны критерий достижимого принимающего цикла, SCC и построение циклического контрпримера. Для одиночной SCC явно требуется петля; собственная принимающая тупиковая вершина 3 демонстрирует исключение. Преобразование LTL в автомат не используется.

Игра достижимости: цикл графа не определяет победителя

В игре на графе недостаточно найти один путь к цели: часть переходов выбирает противник. Аттрактор учитывает владельца вершины и выделяет состояния, из которых цель гарантирована. Построим выигрышную стратегию и отдельную стратегию удержания вне цели.

Перед началом: Ориентированный граф и достижимость; Стратегия при полном наблюдении состояния.

Один граф, два правила выбора

Вершины конечного графа разделены между игроками 0 и 1. В каждом состоянии владелец выбирает следующий переход. У каждой вершины есть хотя бы один преемник. Игрок 0 выигрывает, если когда-нибудь посещается целевое множество G; бесконечное избегание цели означает его проигрыш. Случайных переходов и скрытых состояний в модели нет.

Из своей вершины игроку 0 достаточно иметь один надёжный ход. Из вершины противника требуется, чтобы каждый возможный ответ оставался надёжным. Поэтому простой поиск существующего пути завышает выигрышную область. С другой стороны, требование безопасности каждого ребра и в собственных вершинах было бы слишком сильным: игрок 0 вправе не выбирать плохой доступный переход.

Аттрактор и ранговое доказательство

Начнём с A0=G. На очередном шаге добавляем вершины игрока 0 хотя бы с одним преемником в текущем множестве и вершины игрока 1, у которых все преемники уже там. Добавление повторяется до неподвижной точки A. Новая вершина получает ранг — номер первого шага, на котором она вошла в множество.

В своей вершине положительного ранга игрок 0 выбирает преемника меньшего ранга. В вершине игрока 1 все преемники уже имели меньшие ранги при её добавлении. Поэтому на каждом шаге до цели ранг строго уменьшается; цель достигается не позже числа переходов, равного исходному рангу. Вне A игрок 1 может сохранять игру вне A, а игрок 0 не имеет хода внутрь A. Это доказывает точность полученной выигрышной области.

Управляемый обход опасной ветви

Пусть 0 принадлежит игроку 0 и ведёт в 1 либо 2. Вершина 1 принадлежит игроку 1 и ведёт в 3 либо 4. Вершина 2 также принадлежит игроку 1, но имеет только ход в 5. Вершина 5 принадлежит игроку 0 и ведёт в 3. Цель 3 имеет самопетлю, а нецелевая 4 принадлежит игроку 0 и тоже имеет только самопетлю.

Аттрактор растёт так: {3}, затем{3,5}, затем{2,3,5}, наконец{0,2,3,5}. Стратегия 0→2→5→3 гарантирует успех. Из 1 противник выбирает 4, после чего цель недостижима. Наличие пути 1→3 не делает 1 выигрышной: решающий выбор принадлежит другому игроку. Если изменить владельца 1 на игрока 0, та же геометрия рёбер даст другой результат.

Не всякий путь к цели можно навязать противнику

Условие. На описанной арене из шести вершин цель G={3}. Вычислите аттрактор игрока 0, выберите ход из 0 и объясните проигрыш из 1.

  1. A0={3}; вершина 5 игрока 0 имеет ход в 3 и добавляется на первом шаге.
  2. Вершина 2 игрока 1 имеет единственный преемник 5, поэтому добавляется на втором шаге.
  3. Из 0 игрок 0 выбирает 2, поэтому 0 добавляется на третьем шаге. Вершина 1 не добавляется из-за хода противника в 4; 4 остаётся вне цели навсегда.
  4. Выигрышная область{0,2,3,5}. Из 0 выбираем 2, далее принудительно 5, затем 3. Из 1 противник выбирает 4 и удерживает проигрыш.

Ответ. Игрок 0 выигрывает из 0,2,3,5; из 1 и 4 гарантировать цель нельзя. Ход из 0 должен вести в 2.

Проверка. Ранги вдоль выигрышного пути равны 3,2,1,0. Вне аттрактора вершина 1 имеет ответ 4, а 4 не имеет выхода к цели. Эти две проверки дают стратегии обеих сторон, а не только найденный путь.

Где легко ошибиться. Учитывайте владельца каждого выбора: существование ребра к цели не означает возможности заставить противника его выбрать.

Проверьте понимание

Какой первый ход гарантирует игроку 0 достижение цели из 0?

Вопросы к этой главе

Почему стратегия может не помнить историю?

В рассмотренной конечной игре достаточно выбирать ход по текущей вершине и её рангу. Сам ранговый аргумент гарантирует продвижение к цели.

Наличие цикла всегда означает проигрыш?

Нет. Цель может иметь самопетлю, но её посещение уже является победой. Важно, может ли противник обеспечить бесконечное избегание цели до первого посещения.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

Паритетная игра оценивает бесконечные циклы по приоритетам

В игре достижимости достаточно однажды посетить цель. Условие чётности устроено иначе: важны вершины, к которым игра возвращается бесконечно. На арене из трёх состояний найдём надёжный ход и покажем, как тот же граф допускает проигрышную стратегию, хотя внутри его сильной компоненты имеется большой чётный приоритет.

Перед началом: Ориентированные циклы; Стратегия и выбор противника.

Бесконечный хвост важнее начального посещения

Конечная арена полного наблюдения без тупиков. Используется соглашение: чётность максимального приоритета, встречающегося бесконечно часто.

У каждой вершины заданы владелец и целый неотрицательный приоритет. Игрок Чётный выбирает ребро в своих вершинах, Нечётный — в своих. Они видят текущее состояние и всю историю. Поскольку тупиков нет, получается бесконечная последовательность. Отбросим приоритеты, появившиеся лишь конечное число раз. Если максимальный из оставшихся чётен, выигрывает Чётный; иначе выигрывает Нечётный.

Однократный визит к вершине с приоритетом сто ничего не решает, если затем навсегда повторяется нечётная тройка. Обратная ошибка — объявлять проигрыш после первого нечётного состояния: позднейшие бесконечные возвраты к большей четвёрке его перекрывают. В литературе встречается соглашение о минимальном бесконечно повторяемом приоритете; переносить ответ между соглашениями без перенумерации нельзя.

Стратегия ограничивает возможные циклы

Позиционная стратегия фиксирует один выход в каждой собственной вершине. После фиксации противник всё ещё выбирает свои выходы. Нужно проверить все допускаемые им бесконечные продолжения, а не только нарисовать благоприятный цикл. Полная сильная компонента может содержать сразу хорошие и плохие циклы; максимум её меток не обязан встречаться в каждой игре.

Если стратегии обоих игроков позиционные и фиксированы, у каждой вершины остаётся ровно один выход. Любой старт после конечного префикса попадает в цикл. Тогда чётность максимума этого цикла вычисляется непосредственно. Для маленькой арены можно перебрать все пары таких стратегий. Общая позиционная определённость конечных игр чётности оправдывает этот способ проверки; для нашей выигрышной стратегии дополнительно дадим прямой аргумент, не ограничивающий память противника.

Как доказывается бесконечный возврат

Рассмотрим вершины s,a,b с приоритетами соответственно 1,4,3. Вершины s и b принадлежат Чётному, a — Нечётному. Из s есть выходы в a и b; из a — в a и b; из b — в a и b. Выберем в b ход в a. Тогда после каждого попадания в b следующий шаг обязательно посещает a.

Если Нечётный остаётся в a, приоритет четыре повторяется постоянно. Если он выбирает b, Чётный немедленно возвращает игру в a. Значит a посещается бесконечно при любой истории решений противника. Больших приоритетов нет, поэтому бесконечный максимум равен четырём. Этот аргумент показывает именно гарантию, а не существование удачного продолжения.

Выход из b меняет победителя

Условие. На описанной трёхвершинной арене найдите стратегию Чётного из всех стартов. Проверьте альтернативу b→b и объясните, почему сильная связность {a,b} не даёт готового ответа.

  1. При выборе b→a обе возможные реакции в a приводят к повторному посещению a: либо сразу самопетлёй, либо через b. Поэтому максимальный бесконечный приоритет равен 4.
  2. Из s можно выбрать a или b: после одного шага работает тот же аргумент. Из a и b стратегия также выигрывает. Выигрышная область Чётного — все три вершины.
  3. При альтернативе b→b противник в a выбирает b. Затем игра остаётся в b с единственным бесконечным приоритетом 3. Конечный визит к a с меткой 4 не спасает.
  4. Всего у Чётного четыре позиционные стратегии: два выхода в s и два в b. У Нечётного два выхода в a. Перебор восьми пар подтверждает: из любого старта гарантируют победу ровно две стратегии с b→a.

Ответ. Выбирать b→a; ход из s произволен. Чётный выигрывает из s,a,b. Выбор b→b не даёт гарантии.

Проверка. После фиксации каждой пары стратегий прослеживается путь до первого повтора вершины. Максимумы полученных циклов равны 4 при надёжной стратегии и могут равняться 3 при альтернативной.

Где легко ошибиться. Не подменяйте условие бесконечных повторений максимумом всех меток достижимой компоненты. Противник может навсегда выбрать её меньший подцикл.

Проверьте понимание

Какой выбор в b гарантирует победу Чётного из всех трёх стартов?

Вопросы к этой главе

Разве вершина a с чётной меткой не должна принадлежать Чётному?

Нет. Владелец определяет право выбора следующего ребра, а приоритет — оценку бесконечного поведения. Здесь a специально принадлежит противнику, но стратегия всё равно вынуждает бесконечные возвраты к ней.

Нужно ли посещать s снова?

Нет. Её метка 1 появляется только в начальном префиксе. Условие чётности не меняется от добавления или удаления конечного префикса пути.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Dittmann, Kreutzer, Tomescu: определение игр чётности

    Прочитан раздел3.1: максимальный бесконечный приоритет и позиционные стратегии. Трёхвершинная арена, восемь пар стратегий и прямое доказательство возврата составлены самостоятельно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться