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

В теме Графы и маршруты · Учебная карта
Главная мысль
Избыточная прямая зависимость имеет обходной направленный путь между теми же концами. В ациклическом графе можно удалить такие дуги и сохранить достижимость, получив более короткую запись тех же отношений предшествования. Непосредственные соседи при этом меняются.
Метод и постановка
Уточните смысл стрелки: она обозначает только обязательное предшествование, а не отдельную передачу данных с собственной ценой или физический канал. Если у прямой дуги есть независимое действие, удалять её лишь по существованию обхода было бы другой задачей. Здесь сравнивается отношение наличия направленного пути между вершинами, без сохранения стоимости, пропускной способности и числа способов пройти.
Сначала исключите направленные циклы. В DAG транзитивная редукция однозначна для фиксированного набора вершин. Циклический граф требует дополнительных решений о представлении внутри сильно связных частей и не принимается этим интерфейсом. Топологический порядок сам по себе не удаляет стрелки: он лишь показывает допустимое расположение вершин и не отвечает на вопрос, какие прямые связи уже следуют из других.
Проверка и границы вывода
Для каждой существующей дуги временно уберите только её и проверьте достижимость её конца из начала. Если путь остался, прямую дугу можно исключить. В маленькой сети это можно проверить обычным обходом. Итоговый граф затем сравнивают с исходным по полным множествам достижимости каждой вершины. Такая проверка сильнее сравнения числа дуг или одной выбранной цепочки.
На рисунке с несколькими ветвями важно сохранить все необходимые независимые связи. Две альтернативные дорожки между началом и концом не означают, что можно удалить любой их первый участок одновременно: проверяется именно избыточность прямых дуг в ациклическом отношении. Редукция не выбирает кратчайший маршрут и не обещает сохранить длины путей. После удаления лишней стрелки кратчайший по числу дуг путь может стать длиннее, хотя порядок обязательных зависимостей остаётся тем же. В отчёте полезно предъявить и новую матрицу, и список удалённых пар, чтобы смысл упрощения был проверяемым.
Пример
В сети есть 1→2, 2→3 и 1→3. После временного удаления 1→3 конец остаётся достижим по пути через 2.
Поэтому редукция оставляет две первые дуги. Отношение «1 предшествует 3» сохраняется, но непосредственная стрелка между ними исчезает; число шагов кратчайшего пути меняется с одного до двух.
От чтения к действию
А теперь — вы
Частые вопросы
Достижимость после редукции сохраняется?
Да. Сохраняется наличие пути, но число непосредственных дуг уменьшается.
Можно убрать любую дугу цикла?
Это уже другая постановка. Данный инструмент принимает только ациклические графы, где редукция однозначна.
Углублённый разбор
Доминирующая вершина на каждом пути от старта
Достижимость отвечает, существует ли путь;доминирование — проходит ли каждый путь через выбранную вершину. Пересечение множеств предшественников позволяет находить такие обязательные точки даже в графе с циклами.
Перед началом: Направленный путь; Пересечение множеств.
Зафиксируйте старт и ограничьтесь достижимой частью
Вершина d доминирует над v относительно s, если каждый путь из s в v содержит d. Сама v и старт s всегда входят в этот набор. Для недостижимой вершины универсальная фраза о всех путях могла бы стать пусто истинной, поэтому здесь такие вершины сначала исключаются. Смена старта меняет саму задачу.
Для v≠s обозначим Dom(v)={v}∪пересечение Dom(u) по всем достижимым непосредственным предшественникам u. Любой путь заканчивается одним из этих переходов, поэтому обязательный более ранний узел должен присутствовать перед каждым возможным входом. Обратно, общий обязательный узел предшественников встречается и на каждом полном пути в v.
Циклы требуют неподвижной точки, а не одного прохода
Инициализируем Dom(s)={s}, а остальные множества всеми достижимыми вершинами. Повторяем пересечительные обновления до остановки. Множества могут только уменьшаться, поэтому конечный граф гарантирует завершение. Начальная верхняя оценка сохраняет все настоящие доминаторы;если узел не обязателен, конечный путь-свидетельство постепенно исключает его из соответствующих пересечений.
Для DAG достаточно согласованного топологического прохода. При циклах такого порядка нет, и один произвольный обход может оставить лишние элементы. Непосредственный доминатор является ближайшим строгим обязательным предком;он задаёт дерево, но не обязательно соединён с вершиной прямой исходной дугой.
Удаление даёт независимый смысловой тест
Для d≠s,v можно удалить d и проверить достижимость v из s. Если она исчезла, d был доминатором;если осталась, найден путь, который его обходит. Это медленнее хорошего общего алгоритма при проверке всех пар, зато даёт короткое независимое свидетельство конкретного ответа.
Доминирование касается всех путей, не только кратчайших либо длиннейших. Вершина может находиться во всех оптимальных маршрутах и всё же не доминировать, если существует более дорогой обход. Также наличие пути d→v само по себе ничего не говорит об обязательности d: необходимо исключить остальные пути от заданного старта.
Обязательный выход после обходного входа
Условие. Дуги:s→a,s→b,a→c,b→c,c→b,c→d,a→d,d→t. Найдите Dom(c),Dom(d),Dom(t) и проверьте обязательность c для t.
- В c можно прийти через a или b. Общими остаются только s и сама c, поэтому Dom(c)={s,c}. Цикл b↔c этого вывода не меняет.
- В d есть путь s→a→d, обходящий c, и путь s→b→c→d, обходящий a. Поэтому Dom(d)={s,d}.
- В t входит только d, значит Dom(t)={s,d,t}. Непосредственный доминатор t равен d.
- Удаление d делает t недостижимой. Удаление c оставляет путь s→a→d→t, поэтому c не доминирует над t.
Ответ. Dom(c)={s,c},Dom(d)={s,d},Dom(t)={s,d,t};c не обязателен для t.
Проверка. Перечисление всех простых путей из s в каждую цель и пересечение их вершин даёт те же множества. Циклические обходы не создают новых обязательных узлов: из пути можно удалить замкнутые фрагменты.
Где легко ошибиться. Не подменяйте «каждый путь»одним найденным маршрутом или всеми оптимальными маршрутами. Для отрицательного ответа достаточно одного любого обходящего пути.
Проверьте понимание
Вопросы к этой главе
Зависит результат от весов дуг?
В данном определении нет. Веса не участвуют в существовании пути. Если ограничить допустимую стоимость, получится уже иное относительное понятие обязательности.
Почему нужны только достижимые предшественники?
Недостижимая вершина не может быть последним узлом пути от s. Её включение в пересечение могло бы искусственно изменить задачу без реального маршрута-свидетеля.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- NetworkX: immediate_dominators
Официальная документация: прочитан договор достижимых вершин и дерева непосредственных доминаторов. Простой пересечительный алгоритм, цикл и проверка удалением в главе выведены отдельно; оптимальный алгоритм Lengauer—Tarjan не заявляется.
Неединственность сокращения графа с циклами
Сохранение достижимости в циклическом графе не задаёт единственный самый короткий набор дуг. Более того, подграф, из которого уже нельзя удалить одну дугу, может иметь больше дуг, чем настоящий минимум.
Перед началом: Сильная связность; Минимальность по включению.
Уточните, какая минимальность требуется
Подграф на тех же вершинах эквивалентен исходному по достижимости, если сохраняет все пары, соединяемые направленным путём. Минимальный по включению означает, что ни одну оставшуюся дугу нельзя удалить без потери этого свойства. Минимальный по числу дуг означает наименьшую мощность среди всех эквивалентных подграфов.
Вторая задача сильнее первой. Любой минимум мощности минимален по включению, но обратное неверно. Локальная процедура последовательного удаления избыточных дуг гарантирует лишь первый тип результата и может зависеть от порядка. Название «редукция»без уточнения критерия не объясняет, какое из этих обещаний выполнено.
Внутри сильной компоненты возможны разные скелеты
В полном двунаправленном графе на трёх вершинах достаточно ориентированного цикла: он делает любую вершину достижимой из любой другой. Цикл можно выбрать в двух направлениях, и получаются разные подграфы одинакового минимального размера. Единственность, характерная для транзитивной редукции DAG, здесь исчезает.
Нижняя граница проста: в сильно связном графе на n>1 вершинах каждая имеет хотя бы одну исходящую дугу, значит дуг не меньше n. Достичь границы можно только тогда, когда все исходящие степени равны 1 и весь граф образует один направленный цикл. Обнаружение такого цикла является отдельным структурным требованием, не следующим из одной сильной связности.
Проверяйте удаление на текущем графе
Если каждая исходная дуга имеет обход, нельзя удалить все такие дуги одновременно: обходы могут использовать друг друга. Корректная локальная процедура после каждого удаления обновляет рабочий граф и снова проверяет полную достижимость. Она остановится на включительно минимальном решении, но не докажет минимум мощности.
Для малого примера можно перебрать все подмножества дуг и сравнить отношения достижимости. Это даёт независимую нижнюю границу. Само число сильных компонент недостаточно: разбиение может совпасть, но связи между разными компонентами измениться. Сравнивать нужно именно все исходно достижимые упорядоченные пары.
Три дуги против четырёх необходимых по отдельности
Условие. Исходный граф содержит все шесть дуг между различными A,B,C. Сравните цикл A→B→C→A и двунаправленный путь A↔B↔C.
- Оба подграфа сильно связны, поэтому сохраняют все шесть ненулевых пар достижимости исходного графа.
- Цикл содержит 3 дуги. Меньше 3 невозможно, поскольку каждой из трёх вершин нужен исходящий переход.
- Двунаправленный путь содержит 4 дуги. Удаление любой из них уничтожает достижимость через соответствующее направление разреза, так что он минимален по включению.
- Тем не менее 4 не является минимумом числа дуг, поскольку цикл уже даёт 3. Обратный цикл C→B→A→C показывает неединственность даже оптимального результата.
Ответ. Минимум мощности 3; двунаправленный путь с 4 дугами лишь минимален по включению.
Проверка. Перебор 64 подмножеств шести дуг находит ровно два сильно связных подграфа размера 3. Все четыре удаления из двунаправленного пути по отдельности нарушают сильную связность.
Где легко ошибиться. Отсутствие удаляемой одной дуги не является доказательством глобально минимального числа дуг. И не удаляйте одновременно все связи, обходы которых проверены на старом полном графе.
Проверьте понимание
Вопросы к этой главе
Можно свернуть сильные компоненты?
Да, между ними получится DAG, где есть однозначная транзитивная редукция отношения компонент. Но выбор внутреннего сильно связного скелета остаётся дополнительной задачей.
Нужны ли те же веса после редукции?
В этой постановке веса вообще не сохраняются. Если важны стоимости, ёмкости или число маршрутов, одного совпадения достижимости недостаточно.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- NetworkX: transitive_reduction
Прочитаны сохранение достижимости и ограничение API только DAG из-за неединственности с циклами. Собственные минимальные по включению/числу дуг подграфы и конечный перебор главы не взяты из примера документации.
Размерность частичного порядка: сколько линейных порядков надо пересечь
Один топологический список добавляет сравнения, которых не было в исходных зависимостях. Размерность частичного порядка измеряет, сколько таких списков нужно пересечь, чтобы все искусственные сравнения исчезли. Для точного ответа требуется и семейство списков, и доказательство невозможности меньшего семейства.
Перед началом: Частичный порядок и несравнимые элементы; Линейное расширение ациклических зависимостей.
Пересечение сохраняет только общие сравнения
Линейное расширение конечного порядка P располагает все элементы в ряд и соблюдает каждое строгое сравнение P. Семейство расширений реализует P, если x предшествует y во всех его списках ровно тогда, когда x<y в P. Для несравнимой пары должны встретиться оба направления. Иначе пересечение ошибочно объявит её сравнимой.
Размерность dim(P) — минимальное число списков в таком семействе. Здесь минимизируется число разных представлений одного отношения, а не число цепей в разбиении множества. Ширина и размерность отвечают на разные вопросы. Даже проверка всех заданных дуг в каждом списке недостаточна: она подтверждает расширения, но ещё не подтверждает их точное пересечение.
Несовместимые обращения дают нижнюю границу
Рассмотрим шесть элементов a1,a2,a3,b1,b2,b3. Единственные строгие отношения имеют вид ai<bj при i≠j. Три пары ai,bi несравнимы. В реализующем семействе для каждой из них нужен хотя бы один список с bi раньше ai. Без этого направление ai<bi попадёт в пересечение.
Один список не может обратить две такие пары. Если bi<ai и bj<aj при разных i,j, исходные отношения ai<bj и aj<bi вынуждают замкнутую цепь bi<ai<bj<aj<bi. Строгий линейный порядок цикла не допускает. Следовательно, требуются хотя бы три списка. Эта нижняя граница учитывает совместимость обращений, а не просто количество несравнимых пар.
Сертификат проверяют по всем парам
Для верхней границы нужно предъявить три списка и вычислить их пересечение. Удобно хранить позицию каждого элемента в каждом списке. Для каждой упорядоченной пары различных элементов проверяется, направлена ли она одинаково во всех списках. Результат должен совпасть с полной достижимостью исходных зависимостей, а не только с их сокращённым набором дуг.
В небольшом примере независимая проверка может перечислить все линейные расширения и испытать все пары списков. Она подтверждает невозможность двух представлений непосредственно. Для больших порядков такой перебор быстро растёт; тогда явные несовместимые обращения служат компактным доказательством нижней границы, а предъявленное семейство — проверяемой верхней границей.
Три списка для стандартного шестичленного порядка
Условие. Для отношений ai<bj при i≠j, где i,j принадлежат {1,2,3}, найдите размерность порядка и предъявите реализующее семейство.
- Пары a1,b1; a2,b2; a3,b3 несравнимы. Каждая требует хотя бы одного списка с соответствующим b раньше a.
- Два разных обращения в одном списке дали бы строгий цикл через два исходных перекрёстных сравнения. Поэтому размерность не меньше трёх.
- Возьмём L1=(a2,a3,b1,a1,b2,b3), L2=(a1,a3,b2,a2,b1,b3), L3=(a1,a2,b3,a3,b1,b2). Все шесть обязательных сравнений соблюдены в каждом списке.
- Каждая пара ai,bi обращается в своём списке. Для любых двух a и любых двух b также встречаются оба порядка: это проверяется непосредственно по позициям в трёх списках.
- Иных сравнений в пересечении нет. Верхняя граница три совпала с нижней, поэтому dim(P)=3.
Ответ. Размерность равна 3; семейство L1,L2,L3 точно восстанавливает исходный порядок.
Проверка. Перебор 720 перестановок выделяет все допустимые расширения. Ни одна пара этих расширений не даёт нужного пересечения, а указанная тройка даёт ровно шесть строгих отношений.
Где легко ошибиться. Не принимайте три произвольных топологических списка за реализующее семейство. Необязательное сравнение, одинаковое во всех списках, изменяет восстановленный порядок.
Проверьте понимание
Вопросы к этой главе
Почему нельзя просто обратить каждый список целиком?
Полное обращение нарушает все обязательные отношения ai<bj. Менять направление можно только для несравнимых пар, продолжая соблюдать исходные зависимости.
Достаточно ли обратить только три пары ai,bi?
Для общего порядка такой проверки недостаточно. В данном семействе дополнительно проверяются пары внутри слоя a и внутри слоя b; их направления тоже не должны стать общими для всех списков.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- W. T. Trotter: теория размерности порядков
Определения реализующего семейства и размерности; стандартный пример Sn и препятствие совместному обращению диагональных пар.
Идеалы частичного порядка образуют конечную дистрибутивную решётку
DAG зависимостей описывает не только допустимые линейные расписания. Набор уже выполненных работ должен содержать все предпосылки каждой своей работы, то есть быть нижним идеалом порядка. Все такие наборы образуют решётку с объединением и пересечением. Теорема Биркгофа связывает эту конструкцию со всеми конечными дистрибутивными решётками и показывает, как восстановить исходные зависимости.
Перед началом: Частичный порядок как достижимость DAG; Объединение и пересечение множеств.
Нижний идеал содержит все предпосылки своих элементов
Конечный частичный порядок, заданный DAG достижимости; идеалы являются нижними подмножествами, включая пустое.
Множество I называется нижним идеалом, если из x∈I и y≤x следует y∈I. В модели работ это означает, что нельзя объявить работу завершённой без её обязательных предшественников. Рёбра транзитивной редукции и все отношения достижимости задают одинаковое семейство идеалов: промежуточные предпосылки наследуются по путям.
Объединение двух идеалов остаётся идеалом: элемент объединения принадлежал хотя бы одному из них вместе со всеми предпосылками. Пересечение также замкнуто вниз, поскольку каждая предпосылка принадлежала обоим множествам. Поэтому семейство J(P) упорядочивается включением и имеет операции join=∪ и meet=∩.
Дистрибутивность наследуется от операций множеств
Тождества I∩(J∪K)=(I∩J)∪(I∩K) и двойственное им выполняются как обычные равенства множеств. Все участвующие множества остаются идеалами, значит J(P) является дистрибутивной решёткой. Наличие таких двух операций не означает существования дополнений: множество всех ещё не выполненных работ обычно не замкнуто вниз.
В конечной решётке ненулевой элемент j называют неприводимым по join, если равенство j=x∨y вынуждает j=x либо j=y. В J(P) такими элементами являются ровно главные идеалы ↓p={x:x≤p}. Если ↓p равен объединению двух идеалов, элемент p лежит в одном из них и тянет туда весь ↓p.
Порядок восстанавливается из неприводимых идеалов
Любой идеал I равен объединению ↓p по p∈I. Поэтому неприводимый непустой идеал обязан быть одним из главных: иначе его можно разбить на собственные части. Кроме того, ↓p⊆↓q ровно тогда, когда p≤q. Значит решётка идеалов хранит исходный порядок в подмножестве своих неприводимых элементов.
Общая конечная теорема Биркгофа утверждает обратное: любая конечная дистрибутивная решётка изоморфна решётке идеалов порядка своих join-неприводимых. Отображение посылает элемент a в множество неприводимых j≤a. Здесь существенны конечность и дистрибутивность; произвольная решётка не обязана иметь такое представление операциями объединения и пересечения.
Двенадцать допустимых завершённых наборов
Условие. Порядок содержит зависимости a<b,a<c,b<d,c<d; элемент e независим от всех остальных. Найдите число нижних идеалов и join-неприводимые идеалы. Для I={a,b,e}, J={a,c} вычислите meet и join.
- На четырёх связанных элементах возможны ровно ∅,{a},{a,b},{a,c},{a,b,c},{a,b,c,d}. Например, добавить d без обоих b,c нельзя.
- Независимый e можно включить или исключить в каждом из шести случаев. Получаем 6·2=12 идеалов; это значительно меньше всех 32 подмножеств пяти элементов.
- Пять главных идеалов равны {a},{a,b},{a,c},{a,b,c,d},{e}. Они и только они неприводимы по объединению. Их включения восстанавливают исходный ромб зависимостей и отдельный элемент e.
- Пересечение I,J равно {a}, объединение равно {a,b,c,e}; оба набора допустимы. Дополнение I в полном множестве равно {c,d} и не является идеалом: у c отсутствует предпосылка a, а у d также b.
Ответ. Идеалов 12, join-неприводимых 5. I∧J={a}, I∨J={a,b,c,e}; решётка не является решёткой всех подмножеств.
Проверка. Независимый перебор 32 масок проверяет условие для всех отношений достижимости и оставляет 12. Перебор пар собственных идеалов подтверждает неприводимость ровно пяти главных; все тройки идеалов удовлетворяют обеим дистрибутивным формулам.
Где легко ошибиться. Не считайте любой набор вершин допустимым состоянием выполненных зависимостей. Пропущенная нижняя предпосылка нарушает идеальность, даже если выбранный набор выглядит независимым в сокращённом рисунке.
Проверьте понимание
Вопросы к этой главе
Изменит ли семейство идеалов добавление транзитивной дуги a→d?
Нет. Эта зависимость уже следует по путям через b и c. Идеалы зависят от всего частичного порядка, поэтому редукция и транзитивное замыкание дают одинаковое семейство.
Почему пустой идеал не считается неприводимым?
Это нулевой элемент решётки, который исключён из определения join-неприводимости. Иначе он не соответствовал бы никакому элементу исходного порядка при восстановлении.
Сверить определения и условия
Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.
- MIT 18.212 — Lecture 16: distributive lattices
Конечные дистрибутивные решётки, главные идеалы и представление Биркгофа. Порядок из ромба и независимой работы, все маски и операции проверены отдельно.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Минимум цветов требует двух доказательств: раскраски и отказа меньшего числа
Найти точное хроматическое число малого простого графа ограниченным полным поиском и предъявить проверяемую раскраску.
Открыть темуКак стек Хиерхольцера собирает маршрут из использованных рёбер
Построить эйлеров маршрут стеком Хиерхольцера и независимо проверить точное совпадение мультимножества пройденных и исходных рёбер.
Открыть темуСколько полных назначений разрешает совместимость: перманент без знаков перестановок
Посчитать все полные взаимно однозначные назначения по матрице совместимости и объяснить формулу Райзера через включения и исключения.
Открыть тему