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

Когда список смежности выгоднее матрицы

Сравниваем список смежности и матрицу по памяти и операциям, сохраняем направление и вес рёбер и выбираем структуру под разреженность и требуемые запросы.

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

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

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

Списки смежности хранят существующие соседства и обычно требуют O(V+E) памяти. Матрица резервирует O(V²) ячеек, зато позволяет быстро проверить заданную пару вершин. Выбор зависит от плотности графа и операций.

Что хранится для каждой вершины

В ориентированном графе с рёбрами А→Б, А→В, В→Б список А содержит Б и В, список Б пуст, список В содержит Б. Записи обратных рёбер не добавляются, если их нет в условии. Матрица для тех же вершин ставит признак ребра в позиции строки-источника и столбца-приёмника. Направление нельзя потерять при переходе между структурами.

Для неориентированного графа список обычно хранит каждое ребро у обоих концов, а матрица симметрична. Поэтому число записей соседства в таком списке равно 2E без петель, а не числу разных рёбер E. В оценке O(V+E) постоянный множитель 2 не меняет порядок, но в точном подсчёте ипри экспорте данных различие важно.

Как размер и запрос определяют выбор

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

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

Пример

Граф имеет 4 вершины и 3 направленных ребра без повторов. Сколько ячеек у полной матрицы и сколько записей соседства у списка?

Матрица содержит 16 ячеек, список — 3 записи рёбер плюс контейнеры для 4 вершин. Пустые списки тоже сохраняют существование вершин.

Как не перепутать нулевой вес и отсутствие

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

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

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

А теперь — вы

Какой размер полной матрицы смежности для 10 вершин?

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

Матрица всегда экономнее списка?

Нет. При разреженном графе её V² ячеек могут быть намного больше числа существующих рёбер.

Нулевой вес можно безусловно считать отсутствием ребра?

Нет. Если бесплатные переходы допустимы, требуется отдельное обозначение отсутствия.

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

Компактное хранение разреженного графа в CSR

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

Перед началом: Список смежности; Префиксные суммы.

Границы строк отделены от самих соседей

Для n вершин и m записей соседства CSR использует массив соседей indices длины m, массив весов data той же длины и массив indptr длины n+1. Соседи вершины u находятся на полуинтервале indices[indptr[u]:indptr[u+1]]. Последняя граница indptr[n]=m завершает последнюю строку. Поэтому отдельный нулевой вес не используется как маркер отсутствия ребра.

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

Построение требует двух согласованных проходов

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

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

Компактность подходит не каждой последовательности операций

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

Если индексы внутри строки отсортированы, наличие цели можно искать двоичным поиском. Без сортировки приходится просматривать строку. Для проверки корректности формата нужны начало indptr[0]=0, последняя граница m, неубывание границ, допустимые индексы целей и одинаковые длины indices,data. Эти условия проверяют структуру независимо от алгоритма обхода.

Сохранить пустые строки

Условие. Вершины 0,1,2,3. Ориентированные рёбра 0→1 свесом 5,0→3 свесом 0,2→1 свесом 7. Постройте CSR в порядке целей внутри строки.

  1. Степени выхода равны(2,0,1,0). Их префиксные суммы с начальным нулём дают indptr=[0,2,2,3,3].
  2. Соседи строк идут подряд: indices=[1,3,1], а согласованные веса data=[5,0,7].
  3. Строка 1 занимает пустой полуинтервал [2,2), строка 3 — [3,3). У вершины 1 естьвходящие рёбра, но нет исходящих.
  4. Ребро 0→3 занимаетпозицию 1 и имеет явно хранимый нулевой вес. Оно не исчезает при восстановлении графа из трёх массивов.

Ответ. indptr=[0,2,2,3,3], indices=[1,3,1], data=[5,0,7].

Проверка. По каждой паре соседних границ восстановлены ровно три исходные записи. Последний указатель 3 совпадает с длинами обоих массивов, а пустые строки не потеряны.

Где легко ошибиться. Размер indptr равен n+1, а не n. Без последней границы нельзя единообразно определить конец последней строки, особенно когда она пуста.

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

Какой indptr соответствует разобранному графу?

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

Нулевой вес можно хранить?

Да. Наличие задаётся самой записью в indices и data. Удаление явно хранимых нулей является отдельной операцией и может изменить графовую модель.

Можно менять вес без изменения структуры?

Да, если нужная запись уже существует: меняется соответствующий элемент data. Вставка нового индекса является структурным изменением и обычно существенно дороже.

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

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

  • SciPy: csr_matrix

    Официальная документация: вебом проверены data, indices, indptr, границы строк и стоимость структурных изменений CSR. Структура графа и числовые массивы главы подготовлены отдельно.

Матрица смежности считает маршруты с повторениями

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

Перед началом: Матричное произведение; Маршрут в графе.

Промежуточная вершина задаёт разбиение способов

Пусть Aᵢⱼ — число направленных рёбер из i в j. Для простого графа это ноль либо единица. Элемент(A²)ᵢⱼ=ΣₖAᵢₖAₖⱼсчитает выбор первого ребра i→k и второго k→j. Для каждого k способы перемножаются, а по различным промежуточным вершинам складываются, потому что полученные маршруты различны.

По индукции(Aˡ)ᵢⱼ равно числу маршрутов длины ровно l. База l=0 задаётся единичной матрицей: пустой маршрут существует из вершины в неё саму и не существует между разными вершинами. Поэтому A⁰=I имеет комбинаторный смысл, а не является только формальным правилом степеней.

Повторения разрешены самим состоянием подсчёта

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

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

Большая длина не требует перечисления каждого маршрута

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

Для проверки маленького примера полезно независимо перечислить последовательности вершин нужной длины и проверить каждое соседство. Такой перебор подтверждает конкретный элемент степени и одновременно показывает, какие повторения вошли в ответ. Простая проверка достижимости лишь утверждает положительность некоторого счёта, но не его численное значение.

Три шага с возвращениями

Условие. Вершины a,b,c; рёбра a→b,a→c,b→a,b→c,c→c. Найдите число маршрутов длины 3 из a в c.

  1. В порядке a,b,c матрица A имеет строки(0,1,1),(1,0,1),(0,0,1). Петля c→c сохранена.
  2. За два шага из a можно попасть в a одним способом, в b нулём способов, в c двумя. Первая строка A² равна(1,0,2).
  3. Умножение этой строки на столбец c матрицы A даёт 1·1+0·1+2·1=3.
  4. Явные маршруты: a,b,a,c; a,b,c,c; a,c,c,c. Первое возвращение в a и повторения c являются допустимыми.

Ответ. Ровно 3 маршрутадлины 3.

Проверка. Перебор последовательностей двух промежуточных вершин из {a,b,c} оставляет ровно три указанные последовательности. Это независимо проверяет элемент(A³)ₐ꜀.

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

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

Сколько маршрутов длины 3 из a в c в задаче?

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

Можно узнать число маршрутов длины не больше L?

Да, складывают I+A+…+Aᴸ, если пустые маршруты входят в условие. Одна степень Aᴸсчитает только точную длину.

Почему результат может быстро расти?

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

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

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

  • MIT6.042J: Graph Theory

    Первичный учебный материал MIT; вебом прочитан PDF-текст главы Graph Theory о степенях матрицы смежности и подсчёте walks. Предварительный URL другой лекции MIT вернул 404 и не используется как прочитанный источник. Граф и конечный перебор главы подготовлены отдельно.

Общие соседи как пересечение битовых множеств

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

Перед началом: Множества соседей; Двоичная маска.

Один бит соответствует одной вершине

Зафиксируем нумерацию вершин 0,…,n−1 и закодируем N(u) числом Mᵤ=Σ по v∈N(u)2ᵛ. Бит v равен единице ровно тогда, когда v является соседом u. Побитовое И двух масок оставляет единицу только в позициях общих соседей. Поэтому popcount(Mᵤ&Mᵥ)=|N(u)∩N(v)|.

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

Треугольник требует наличия самого ребра

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

Если просуммировать число общих соседей по всем неориентированным рёбрам, каждый треугольник встретится трижды — по одному разу на каждом ребре. Для перечисления без повторов можно требовать u<v<w и оставлять в пересечении только w>v. Это отличается от суммирования по всем упорядоченным парам, где множитель повторов был бы другим.

Модель графа ограничивает смысл маски

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

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

Два треугольника у одного ребра

Условие. Простой неориентированный граф имеет рёбра 01,02,12,13,23,34. Найдите общих соседей 1 и 2 черезмаски и число всех треугольников.

  1. N(1)={0,2,3}, поэтому M₁=1+4+8=13. N(2)={0,1,3}, поэтому M₂=1+2+8=11.
  2. Побитовое пересечение 13&11=9. Единичные биты числа 9 стоятвпозициях 0 и 3, значит общих соседей два.
  3. Они дают треугольники 012 и 123, содержащие ребро 12. Ребро 34 нетреугольно: у вершин 3 и 4 нетобщегососеда.
  4. При суммировании по всем шести рёбрам общий счёт равен 6; деление на 3 даёт два треугольника во всём графе.

Ответ. Общие соседи {0,3}; всего 2 треугольника.

Проверка. Перебор всех троек из пяти вершин оставляет только {0,1,2} и {1,2,3}. Маски сохраняют ровно те же три смежности для каждой принятой тройки.

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

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

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

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

Почему нельзя всегда считать И одной операцией?

Для маски длиннее машинного слова требуется обработать несколько слов. В языках с большими целыми это скрыто внутри операции, но стоимость всё равно зависит от длины маски.

Как избежать деления после перечисления?

Оставляйте только тройки с u<v<w. Для каждого ребра u<v пересекайте соседства и пропускайте биты w≤v; тогда каждый треугольник появляется ровно один раз.

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

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

  • Python: Integer bitwise operations and int.bit_count

    Официальная документация: вебом проверены побитовые операции и число единичных битов. Формула общих соседей и устранение повторов треугольников доказаны в самой главе.

Транзитивное замыкание через последовательное разрешение посредников

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

Перед началом: Матрица смежности; Побитовое ИЛИ.

Инвариант относится к промежуточным вершинам

Пронумеруем вершины 0,…,n−1. Инициализируем R исходными дугами и единичной диагональю, поскольку разрешаем путь длины 0. После шага k матрица описывает пути, у которых все промежуточные вершины принадлежат {0,…,k}. Концы пути при этом не ограничены: индекс k не означает добавление новой строки или новой конечной вершины.

Рекурсия имеет вид R_new[i,j]=R_old[i,j]∨(R_old[i,k]∧R_old[k,j]). Путь либо обходится без k, либо делится в k на два участка с более ранними промежуточными вершинами. Для достижимости можно удалить циклические повторения и выбрать простой представитель, поэтому одного разделения достаточно. После всех k ограничение на промежуточные вершины исчезает.

Одна строка объединяет сразу все назначения

Пусть row[i] — битовая маска всех достижимых из i вершин. На шаге k, если бит k в row[i] установлен, выполняем row[i] |= row[k]. Это одновременно добавляет все j, достижимые через k. Сам row[k] на этом шаге не меняется: объединение с собой ничего не добавляет. Условие достижимости k из i тоже не может впервые возникнуть за счёт одного только k, поэтому обновление на месте сохраняет инвариант.

Цикл по k должен быть внешним. Произвольная перестановка трёх циклов с одним проходом уже не соответствует доказанному ограничению промежуточных вершин. Для машинного слова ширины w объединение строки требует O(ceil(n/w)) операций, общая стоимость O(n²ceil(n/w)), память O(n²) бит. У неограниченного целого Python одна операция OR также зависит от количества его машинных разрядов, а не является бесплатной константой для любого n.

Рефлексивная диагональ требует осторожности при поиске циклов

В принятом замыкании R[i,i]=1 с самого начала для каждой вершины, даже изолированной. Поэтому единица на диагонали сама по себе не доказывает непустой цикл. Для этого можно отдельно вычислять достижимость непустыми путями либо искать взаимную достижимость различных вершин, а петли проверять отдельно. Соглашение о нулевом пути влияет и на ответы quiz: исходная вершина входит в собственную строку даже без возвратного маршрута.

Строки распространяются через цикл b,c

Условие. Вершины a,b,c,d имеют номера 0,1,2,3; дуги a→b,b→c,c→b,c→d. Найдите рефлексивное замыкание в битовых масках и множество достижимых из b.

  1. Начальные маски равны 3,6,14,8: например, row[c]=14 содержит биты b,c,d, а row[d]=8 содержит только d.
  2. Шаг k=a ничего не добавляет. На шаге b строка a объединяется со строкой b и становится 7, добавляя достижимость c.
  3. На шаге c строки a и b объединяются с14. Получаем row[a]=15,row[b]=14,row[c]=14,row[d]=8. Последний шаг d новых битов не добавляет.
  4. Итак, из b достижимы b,c,d. Вершина a не достижима обратно, хотя из неё можно попасть в цикл. Нулевой путь включает b в ответ.

Ответ. Итоговые маски (15,14,14,8); из b достижимы {b,c,d}.

Проверка. Четыре независимых обхода графа находят те же множества. Отдельно проверено, что путь b–c–d существует, обратного пути к a нет, а диагональ d включена только по соглашению о пустом пути.

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

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

Каково множество достижимых из b при разрешённом пути длины 0?

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

Можно ли получить замыкание только для DAG?

Нет, метод работает и с циклами. Именно цикл b↔c в примере показывает, что топологический порядок не нужен. Все k выбираются по произвольной фиксированной нумерации вершин.

Почему OR не добавляет лишние вершины?

Каждый добавленный бит j имеет два уже удостоверенных участка i→k и k→j. Их склейка является реальным путём, поэтому обновление сохраняет отсутствие ложной достижимости. Индукция даёт также полноту всех допустимых путей.

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

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

  • Daniel Jiménez: Analysis of Algorithms, Lecture19

    Прочитаны рефлексивная инициализация t⁰, инвариант промежуточных вершин{1,…,k} и рекурсия Уоршелла. Битовое объединение строк и собственный четырёхвершинный граф получены отдельно; оценки Дейкстры из вступления источника здесь не используются.

Времена DFS различают дерево, обратную, прямую и перекрёстную дугу

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

Перед началом: Рекурсивный DFS и три цвета вершин; Ориентированная дуга и предок в дереве.

Интервалы открытых вызовов вложены либо не пересекаются

При открытии вершины u увеличиваем общий счётчик и записываем d[u]. После обработки всех её исходящих дуг снова увеличиваем счётчик и записываем f[u]. Серый цвет соответствует незавершённому рекурсивному вызову, чёрный — уже завершённому. Числа относятся к одному полному DFS-лесу, включая новые корни после окончания первой компоненты обхода.

Если v является собственным потомком u, то d[u]<d[v]<f[v]<f[u]. Для разных поддеревьев, не связанных отношением предка, временные интервалы не пересекаются. Частично перекрывающихся интервалов быть не может: рекурсивный вызов либо завершится до следующего, либо будет полностью содержать вложенный вызов. Это свойство часто называют скобочной структурой DFS.

Родитель отделяет древесную дугу от прямой

Древесная дуга u→v впервые обнаружила белую v, поэтому parent[v]=u. Обратная дуга направлена к серому предку; петля в текущую вершину тоже относится к обратным. Недревесная дуга к собственному потомку называется прямой. Её временные интервалы вложены так же, как у древесной дуги, поэтому одних времён для различения этих двух типов недостаточно.

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

Порядок соседей входит в воспроизводимость примера

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

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

Один лес содержит все четыре типа

Условие. Порядок вершин a,b,c,d,e,f. Списки соседей: a:[b,c,d], b:[c], c:[b], d:[c], e:[f], f:[d]. Выполните полный DFS и классифицируйте недревесные дуги.

  1. Из a открываются b и c. Получаем интервалы c:[3,4], b:[2,5]. Дуга c→b видит серого предка и является обратной.
  2. После возврата к a дуга a→c ведёт в завершённого потомка: она прямая, а не древесная. Затем a открывает d с интервалом [6,7].
  3. Дуга d→c соединяет непересекающиеся интервалы [6,7] и [3,4], поэтому она перекрёстная. Вершина a завершается с интервалом [1,8].
  4. Следующий белый корень e получает [9,12], его ребёнок f — [10,11]. Дуга f→d пересекает границу деревьев и тоже является перекрёстной.
  5. Древесные дуги: a→b,b→c,a→d,e→f. Времена образуют все числа от одного до двенадцати без повторов; единственная обратная дуга c→b подтверждает цикл b→c→b.

Ответ. a→c — прямая; c→b — обратная; d→c и f→d — перекрёстные. Остальные четыре дуги древесные.

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

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

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

Каков тип дуги d→c в указанном обходе?

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

Почему parent нужен, если известны все времена?

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

Можно ли остановиться после обхода из a?

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

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

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

  • Boost Graph Library 1.82: depth-first search

    Прочитаны псевдокод DFS с предшественниками и временными метками и описание цветовых событий. Это закреплённая версия документации, не утверждение об актуальной версии библиотеки. Конкретный лес и разделение прямых/перекрёстных дуг по интервалам проверены отдельно.

Древесное разложение: динамика помнит только границу

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

Перед началом: Независимое множество графа; Динамическое программирование и разделители.

Что должно хранить корректное древесное разложение

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

Ширина разложения равна максимальному размеру мешка минус один. Древесная ширина графа — минимум этой величины по всем допустимым разложениям. Большой мешок всегда позволяет формально построить разложение, но не делает алгоритм быстрым. Выигрыш возникает при малой границе, когда число возможных граничных подмножеств ограничено величиной порядка 2^(w+1).

Почему хватает пересечения мешков

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

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

Два мешка для одного цикла

Пусть рёбра графа образуют цикл 0–1–2–3–0. Возьмём мешки B₁={0,1,2} и B₂={0,2,3}; их пересечение S={0,2}. Каждое ребро покрыто, а общие вершины присутствуют в обоих соседних мешках. Это разложение ширины 2. Для каждого T⊆S определим fᵢ(T) как максимум числа выбранных вершин в мешке Bᵢ при точном выборе T на общей границе.

Для T=∅ оба локальных максимума равны 1: можно взять частные вершины 1 и 3. Для T={0} или {2} локальные максимумы также равны 1, но их сумма после вычитания границы даёт только 1. Для T={0,2} оба значения равны 2, а объединённый результат равен 2+2−2=2. Перебор четырёх граничных состояний даёт максимум 2 без перебора всех подмножеств большого исходного графа.

Граница не должна считаться дважды

Условие. Для цикла 0–1–2–3–0 и мешков {0,1,2}, {0,2,3} вычислите независимое число через состояния на S={0,2}. Локальные значения включают саму границу.

  1. При T=∅ можно независимо выбрать 1 в первом мешке и 3 во втором. Получаем 1+1−0=2.
  2. При T={0} все частные вершины соседствуют с 0. Оба локальных значения равны 1; итог 1+1−1=1. Для T={2} получается то же.
  3. При T={0,2} общие вершины не соединены ребром, поэтому оба локальных значения равны 2. Итог равен 2+2−2=2.
  4. Максимум четырёх состояний равен 2. Его достигают независимые множества {1,3} и {0,2}.

Ответ. Независимое число равно 2. При соединении локальных таблиц вычитают |T|.

Проверка. Ни одно трёхэлементное подмножество цикла не независимо: после удаления любой одной вершины среди оставшихся остаётся ребро. Полный перебор 16 подмножеств подтверждает верхнюю границу 2.

Где легко ошибиться. Значение 2+2=4 при T={0,2} — не большое независимое множество, а двойной подсчёт одной и той же границы. Договорённость о составе локального значения должна быть записана явно.

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

Чему равно объединённое значение для T={0,2}, если оба локальных значения равны 2 и включают границу?

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

Любое разбиение графа на маленькие множества подойдёт?

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

Означает ли пример полиномиальное решение для всех графов?

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

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

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

Джонсон перечисляет простые ориентированные циклы без вращательных дублей

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

Перед началом: Сильно связные компоненты ориентированного графа; Рекурсивный поиск и стек текущего пути.

Минимальная вершина устраняет вращательные повторы

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

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

Цикл не может проходить через разные сильные компоненты: движение по нему даёт взаимную достижимость. А удаление s безопасно для следующих этапов, поскольку все циклы с минимальной вершиной s уже выведены. Компоненты нужно пересчитывать после удаления; первоначальная большая компонента может распасться.

Blocked хранит больше информации, чем присутствие в стеке

Процедура circuit(v) кладёт v в стек и помечает blocked[v]. Дуга в s завершает цикл; в другую вершину рекурсивно идём только при отсутствии блокировки. После возврата из неудачного поиска v может оставаться заблокированной, даже когда уже снята со стека. Это предотвращает повторное исследование заведомо бесполезного продолжения в неизменившемся контексте.

Если из v не удалось вернуться к s, добавляем v в списки B[w] её соседей. Смысл зависимости: неудача v может перестать действовать после разблокировки w. Если цикл через v найден, вызываем unblock(v), снимаем её блокировку и рекурсивно разблокируем элементы B[v], очищая зависимости. Постоянный visited вместо этой процедуры потерял бы циклы.

Размер результата входит в оценку времени

Циклов может быть экспоненциально много, поэтому обещание времени только O(n+m) для полного списка невозможно. Для алгоритма Джонсона стандартная оценка O((n+m)(c+1)), где c — число выведенных простых циклов; вспомогательная память линейна без хранения всего вывода. Это отличается от задачи нахождения одного свидетеля цикла.

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

После удаления начала остаются новые циклы

Условие. Вершины 0,1,2,3,4. Дуги 0→1, 1→2, 2→0, 1→3, 3→2, 2→3, 3→4, 4→1. Перечислите все простые ориентированные циклы в записи с минимальной вершиной первой.

  1. Все пять вершин сначала сильно связны. При старте 0 получаем цикл 0,1,2 и альтернативу 0,1,3,2. Замыкающая дуга в обоих случаях 2→0.
  2. Продолжение 0,1,2,3,4 не может замкнуться в 0 без повторного посещения 1. Оно не даёт нового простого цикла через текущий старт; зависимости блокировки затем должны сниматься при успешном альтернативном продолжении.
  3. Удаляем 0. В оставшейся компоненте со стартом 1 получаем циклы 1,2,3,4 и 1,3,4, каждый с замыканием 4→1.
  4. Удаляем 1. Остаётся двухвершинная циклическая компонента {2,3}, дающая цикл 2,3 через дугу 3→2. После удаления 2 циклических компонент больше нет.

Ответ. Ровно пять циклов: (0,1,2), (0,1,3,2), (1,2,3,4), (1,3,4), (2,3). Замыкающая вершина в списках не повторяется.

Проверка. Независимый перебор всех перестановок подмножеств оставляет эти пять записей после нормировки минимальным началом. Их длины 3,4,4,3,2; каждая внутренняя и замыкающая дуга присутствует в исходном условии.

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

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

Сколько простых ориентированных циклов с точностью до вращения имеет разобранный граф?

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

Почему цикл 2,3 выводится отдельно, хотя его вершины уже встречались?

Раньше они входили в пути с другим фиксированным началом. После удаления меньших вершин этот цикл имеет собственный минимальный старт 2 и должен быть выведен ровно один раз.

Почему цикл 0,1,2 нельзя дополнительно вывести как 1,2,0?

Это вращение того же ориентированного обхода. Договорённость о минимальном начале и последовательное исключение вершин отводят ему единственный внешний этап.

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

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

Обхват невзвешенного графа: кратчайший цикл из BFS-деревьев

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

Перед началом: BFS-расстояния и дерево родителей; Простой цикл неориентированного графа.

Обратная запись древесного ребра не создаёт цикл

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

Выполняем BFS из r, сохраняя расстояния d и родителей. Каждое неориентированное ребро обычно есть в двух списках соседей. Если один конец является родителем другого, это одно древесное ребро, а не цикл длины два. Остальные рёбра между достигнутыми вершинами замыкают простой цикл вместе с путём в BFS-дереве.

Пусть такое ребро соединяет u,v, а z — их наименьший общий предок в дереве. Настоящая длина цикла равна d(u)+d(v)+1−2d(z). До z два пути различны, выше z совпадают и не должны входить в восстановленную запись дважды. Если граф не связен, обходы из других корней отдельно охватывают остальные компоненты.

Минимум оценок по всем корням даёт точное значение

Для длины достаточно сравнивать оценки d(u)+d(v)+1 всех недревесных рёбер во всех полных BFS. Каждая оценка не меньше длины соответствующего настоящего цикла, а значит не меньше обхвата g. Возьмём теперь корень на кратчайшем цикле. Расстояния до его вершин не превосходят длин более коротких дуг этого цикла.

На нечётном цикле длины 2k+1 концы любого его ребра имеют расстояния не больше k. На чётном цикле 2k только одна вершина может требовать k шагов вдоль цикла; остальные требуют не больше k−1. Поэтому для каждого ребра этого цикла сумма расстояний плюс единица не больше g. Хотя бы одно его ребро недревесное, и соответствующая оценка достигает g.

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

Итоговая оценка O(n(n+m)) получается из n полных BFS и просмотра рёбер. Чтобы вернуть свидетель, сохраняем корень, ребро и дерево лучшего кандидата, затем один раз восстанавливаем два пути до общего предка. Не следует выполнять дорогой подъём по родителям для каждого ребра и одновременно объявлять прежнюю оценку времени без дополнительного анализа.

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

Дальний корень скрывает короткий треугольник

Условие. Граф имеет вершины s,r,a,b,u,v,w и рёбра s—r, r—a, a—u, r—b, b—v, u—v, v—w, w—u. Найдите обхват; в BFS из s обрабатывайте a раньше b и u раньше v.

  1. Из s получаем уровни s:0,r:1,a:2,b:2,u:3,v:3,w:4. Родитель w равен u. Недревесные рёбра — u—v и v—w.
  2. Для u—v простая сумма расстояний плюс единица равна 7. Общий предок r имеет глубину 1, поэтому настоящий цикл u—a—r—b—v—u содержит пять рёбер, а не семь.
  3. Ребро v—w даёт оценку 8 и цикл длины 6 после удаления общего хвоста. Один этот BFS поэтому не предъявляет кратчайший треугольник.
  4. Запускаем BFS из u. Вершины v,w имеют расстояние 1, а ребро v—w недревесное. Получаем оценку 1+1+1=3 и цикл u—v—w—u. В простом графе более короткого цикла быть не может.

Ответ. Обхват равен 3. Кратчайший цикл — треугольник u,v,w; произвольный корень s дал только более длинные фундаментальные циклы.

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

Где легко ошибиться. Не интерпретируйте d(u)+d(v)+1 как буквальную длину восстановленного цикла при любом корне. Общая часть путей к корню в этой сумме посчитана дважды.

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

Каков точный обхват семивершинного графа в разобранном примере?

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

Почему нельзя использовать те же правила для двух параллельных рёбер?

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

Что возвращать для дерева?

Отдельный результат «циклов нет», либо бесконечный обхват по принятой математической договорённости. Длина ноль означала бы другой объект и здесь не подходит.

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

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

  • MIT 6.890 — Lecture 10, §2.1

    Восстановление цикла из BFS-дерева через общего предка. Здесь разобран полный просмотр всех недревесных рёбер; он отличается от ранней остановки в алгоритме приближения лекции, точность доказана отдельно.

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

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

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