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

Матрица достижимости: как проверить сжатие ориентированного графа

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

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

Вузовский уровень · Все вузовские темы

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

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

Матрица смежности A хранит прямые дуги, матрица достижимости R — существование направленных путей. Начните с R=A∨I. На этапе k заменяйте клетку Rᵢⱼ значением Rᵢⱼ∨(Rᵢₖ∧Rₖⱼ). После всех этапов вершины одной компоненты определяются взаимными единицами Rᵢⱼ=Rⱼᵢ=1. Прямые дуги конденсации затем восстанавливают по исходной A, а не по всем единицам R.

Развести прямую дугу и существование пути

В квадратной матрице A строка задаёт начало, столбец — конец дуги; единица Aᵢⱼ означает прямой переход i→j. Ноль сообщает отсутствие такой дуги, а не обязательно отсутствие любого пути. Для ручной таблицы достижимости добавьте единицы на диагональ: путь длины ноль существует из каждой вершины в себя. Исходную A сохраните отдельно, потому что она понадобится после замыкания.

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

Проследить изменения по промежуточной вершине

Для контроля ручного расчёта храните отдельную таблицу после каждого разрешённого k. В новой таблице оставьте все прежние единицы; затем добавьте i→j, если в предыдущей таблице одновременно были i→k и k→j. На этапе k допускаются промежуточные вершины с номерами от 1 до k. Концы пути этим ограничением не связаны. После последнего этапа учтены все возможные промежуточные вершины.

Рассмотрим четыре вершины и исходные дуги 1→2, 2→3, 3→2, 3→4. Строки R до промежуточных переходов: «1 1 0 0»; «0 1 1 0»; «0 1 1 1»; «0 0 0 1». Разрешение k=1 ничего не добавляет. При k=2 появляется 1→3, поскольку уже есть 1→2 и 2→3. Обратная достижимость 3→1 из этого не следует: направления сохраняются.

Пример

Продолжите этот расчёт после k=2. Какие клетки добавит k=3, каковы итоговые строки R и группы взаимной достижимости?

Через вершину 3 добавляются 1→4 и 2→4. Новых обратных путей нет; k=4 ничего не меняет. Итоговые строки: «1 1 1 1»; «0 1 1 1»; «0 1 1 1»; «0 0 0 1». Вершины 2 и 3 имеют взаимные единицы; 1 не достижима обратно из них, а 4 не возвращается к ним. Получаются группы {1}, {2,3}, {4}.

Проверить список прямых дуг после объединения

Присвойте этим группам метки C₁={1}, C₂={2,3}, C₃={4}. Теперь снова просмотрите исходные дуги A. Переход 1→2 даёт C₁→C₂, дуги 2→3 и 3→2 остаются внутри C₂ и отбрасываются, а 3→4 даёт C₂→C₃. Повторения одной межгрупповой пары записывают только один раз. Это построение конденсации, а не удаление всех избыточных дуг произвольного графа.

Клетка R₁₄ равна единице, но прямой дуги C₁→C₃ в данном примере нет: исходная A не содержит перехода из первой группы в третью. Есть путь через C₂. Если строить дуги по каждой единице R, получится транзитивное замыкание связей между группами — другой, более плотный граф. Поэтому одной правильной таблицы R недостаточно, если затем перепутать два разных смысла стрелки.

Сверить ручной разбор с конкретным результатом

В инструмент «Компоненты сильной связности и граф конденсации» исходную матрицу вводят в поле «Квадратная матрица 0/1 до 10×10»: числа разделяют пробелами, строки — переносами. Для разобранного примера строки A равны «0 1 0 0»; «0 0 1 0»; «0 1 0 1»; «0 0 0 0». Вводите A, не заменяя её заранее вычисленной R: иначе прямые дуги конденсации изменятся.

Таблица результата этого ввода показывает три группы: {1}, {2,3}, {4}. Под ней приведены прямые дуги конденсации C1 → C2 и C2 → C3. Промежуточные матрицы R инструмент не выводит: их этапы проверьте по ручному разбору выше. Метки групп служат обозначениями, поэтому при другом порядке нумерации сравнивайте состав и связи, а не только номера.

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

А теперь — вы

В исходной A есть только дуги 1→2 и 2→3. После замыкания R₁₃=1, а компоненты — три отдельные вершины. Какие прямые дуги должна содержать конденсация, построенная по исходной A?

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

Почему нельзя сразу вводить в калькулятор матрицу достижимости R?

Группы взаимной достижимости сохранятся, но инструмент восстанавливает прямые дуги конденсации по введённым единицам. Если вместо A подать R, путь может стать дополнительной прямой дугой результата.

Единица на диагонали означает, что в исходном графе была петля?

Нет. При построении R диагональ учитывает путь длины ноль. Исходная матрица A при этом не меняется, и реальная петля в ней по-прежнему определяется собственным значением клетки.

Матрица достижимости сообщает число маршрутов между вершинами?

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

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

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

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