Транзитивная редукция зависимостей DAG

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

Ваш пример

Числа и дроби: 0.5, 0,5 или 1/3. Числа в строке разделяются пробелами, строки — переносом. Выражения не выполняются.

Разбор примера

Удалено избыточных дуг: 1

  1. Циклов нет.
  2. До и после удаления сравнивались все множества достижимости.

Метод и условия расчёта

Сначала проверяем отсутствие направленного цикла.

Дуга u→v избыточна, если после её временного удаления v всё ещё достижима из u.

Теория к методу

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

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

Пример: В сети есть 1→2, 2→3 и 1→3. После временного удаления 1→3 конец остаётся достижим по пути через 2.

Поэтому редукция оставляет две первые дуги. Отношение «1 предшествует 3» сохраняется, но непосредственная стрелка между ними исчезает; число шагов кратчайшего пути меняется с одного до двух.

Вопросы по теме

Достижимость после редукции сохраняется?

Да. Сохраняется наличие пути, но число непосредственных дуг уменьшается.

Можно убрать любую дугу цикла?

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

Графы и маршруты: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.