Дискретная математика: разработайте алгоритм, который за O(n + m) (n — число вершин, m — число рёбер) определяет, имеет ли ориентированный ациклический граф уникальную топологическую сортировку; докажите корректность и проанализируйте, какие структуры графа дают единственность
Задача. Для ориентированного ациклического графа G = V,EV, EV,E∣V∣=n,∣E∣=m|V| = n, |E| = m∣V∣=n,∣E∣=m определить за On+mn + mn+m, имеет ли G единственную топологическую сортировку.
Краткий ответ / идея
Запустить алгоритм Кана KahnKahnKahn для топологической сортировки, но на каждом шаге проверять количество вершин с нулевой входящей степенью. Если когда‑либо оно ≥ 2 — топологическая сортировка не единственна. Если всегда ровно 1 — сортировка единственна.Это даёт время On+mn + mn+m.
Алгоритм вариантнаосновеKahnвариант на основе KahnвариантнаосновеKahn
Вычислить invvv для всех вершин v входящаястепеньвходящая степеньвходящаястепень.Поместить в очередь Q все v с invvv = 0.i := 1.Пока Q не пуста: a. Если |Q| ≥ 2, вернуть "не единственна" (есть >1 возможный выбор). b. v := единственный элемент Q; извлечь v. c. orderiii := v; i := i + 1. d. Для каждого ребра (v -> u) выполнить inuuu := inuuu - 1; если inuuu = 0, добавить u в Q.Если i = n+1 всевершиныобработанывсе вершины обработанывсевершиныобработаны, вернуть "единственна" и, при желании, order; иначе — граф содержит цикл поусловиюциклотсутствуетпо условию цикл отсутствуетпоусловиюциклотсутствует.
Корректность доказательстводоказательстводоказательство
1) Если когда‑то |Q| ≥ 2, то сортировка не единственна.
Пусть в некоторый момент источниками оставшихся вершин являются x и y x≠yx ≠ yx=y. Тогда оба варианта — сначала x потом y, и сначала y потом x — дадут корректные топологические упорядочения (поскольку ни одно из них не зависит от другого — нет ребра y->x и нет ребра x->y от оставшихся вершин), следовательно порядок не уникален.
2) Если всегда |Q| = 1, то сортировка единственна.
Алгоритм Кана даёт некоторую топологическую сортировку order. Предположим существует другая сортировка order' ≠ order. Возьмём первую позицию t, где они различаются: order1..t−11..t-11..t−1 = order'1..t−11..t-11..t−1, а в позиции t разные вершины a = orderttt, b = order'ttt. Но после выбора первых t-1 вершин очередь источников однозначно определяется и по предположению всегда содержит ровно одну вершину, значит нельзя было выбрать и a, и b по-разному — противоречие. Следовательно порядок единственный.
Эквивалентные характеризации единственности Следующие условия эквивалентны для DAG G: A) G имеет единственную топологическую сортировку. B) При выполнении Kahn на каждом шаге ровно одна вершина имеет in = 0. C) В некоторой азначитвединственнойа значит в единственнойазначитвединственной топологической сортировке v1, v2, ..., vn для всех i = 1..n-1 существует ребро vi -> v{i+1}. Тогда для любых i < j существует путь vi -> vj транзитивностьвдольпутитранзитивность вдоль путитранзитивностьвдольпути — то есть отношение достижимости задаёт линейный тотальныйтотальныйтотальный порядок на V.
Доказательство эквивалентности C с A/B:
Если существует i с отсутствующим ребром vi -> v{i+1}, то между vi и v{i+1} нет пути в одну сторону иначемеждунимивпорядкебылабыкакая−топромежуточнаявершинаиначе между ними в порядке была бы какая-то промежуточная вершинаиначемеждунимивпорядкебылабыкакая−топромежуточнаявершина, и значит эти две вершины сопоставимы, и можно их поменять местами в порядке — значит порядок не единственный. Поэтому при единственности ребро между каждым соседним парой обязательно есть.Наличие ребер между всеми соседями даёт путь между любой парой vi, vj черезпоследовательностьсоседнихреберчерез последовательность соседних реберчерезпоследовательностьсоседнихребер, значит любая топологическая сортировка должна сохранить этот порядок по достижимости, следовательно порядок единственен.
Какие структуры графа дают единственность
Это ровно ориентированные цепи directedchainsdirected chainsdirectedchains покрытия всех вершин: DAG имеет единственную топологическую сортировку тогда и только тогда, когда он содержит ориентированный гамильтонов путь v1->v2->...->vn афактическиэтотпутьиестьединственныйпорядока фактически этот путь и есть единственный порядокафактическиэтотпутьиестьединственныйпорядок. Эквивалентно частично упорядоченное множество posetposetposet, заданное графом, является линейным totalorder,chaintotal order, chaintotalorder,chain.Примеры: Единственна: простой путь 1->2->3->...->n любыедополнительныеребра,согласованныесэтимпорядком,допустимы;главное—междулюбымидвумявершинамиболееранняядостижимакболеепозднейлюбые дополнительные ребра, согласованные с этим порядком, допустимы; главное — между любыми двумя вершинами более ранняя достижима к более позднейлюбыедополнительныеребра,согласованныесэтимпорядком,допустимы;главное—междулюбымидвумявершинамиболееранняядостижимакболеепоздней.Не единственна: два независимых пути, пара несравнимых вершин (u и v такие, что нет пути ни u->v ни v->u) — уже дают по крайней мере две топологические сортировки, переставляя эти вершины.
Сложность
Вычисление входящих степеней: On+mn + mn+mпереборвсехрёберперебор всех рёберпереборвсехрёбер.Алгоритм Кана обрабатывает каждое ребро ровно один раз при уменьшении inuuu; операции с очередью — Onnnвставка/удалениевставка/удалениевставка/удаление. Итого On+mn + mn+m.Память: хранение списка смежности On+mn + mn+m и массивов in, order размером Onnn.
Альтернативный эквивалентныйэквивалентныйэквивалентный способ проверки за On+mn + mn+m
Построить любую топологическую сортировку KahnилиDFSKahn или DFSKahnилиDFS.Проверить для каждой соседней пары в полученном порядке, есть ли ребро из предыдущей в следующую вершину. Если для какой‑то пары ребра нет — сортировка не единственна; если есть для всех — единственна. Этот способ корректен по аргументам выше и тоже On+mn + mn+mпроверкуребрамеждусоседямиможноделатьзасуммарноO(n+m),еслихранитсясписоксмежности;длябыстройпроверкикаждогоконкретногоребраможно,например,пометитьсоседейпервойвершинывовременномхешепроверку ребра между соседями можно делать за суммарно O(n + m), если хранится список смежности; для быстрой проверки каждого конкретного ребра можно, например, пометить соседей первой вершины во временном хешепроверкуребрамеждусоседямиможноделатьзасуммарноO(n+m),еслихранитсясписоксмежности;длябыстройпроверкикаждогоконкретногоребраможно,например,пометитьсоседейпервойвершинывовременномхеше.
Итого
Простое и корректное решение: Kahn с проверкой |Q| == 1 на каждом шаге — On+mn + mn+m.Условие единственности: отношение достижимости в DAG — тотальный порядок; в терминах графа — граф содержит ориентированный Hamiltonian path, задающий единственный порядок (эквивалентно: в любой топологической сортировке для всех i есть ребро vi->v_{i+1}).
Задача. Для ориентированного ациклического графа G = V,EV, EV,E ∣V∣=n,∣E∣=m|V| = n, |E| = m∣V∣=n,∣E∣=m определить за On+mn + mn+m, имеет ли G единственную топологическую сортировку.
Краткий ответ / идея
Запустить алгоритм Кана KahnKahnKahn для топологической сортировки, но на каждом шаге проверять количество вершин с нулевой входящей степенью. Если когда‑либо оно ≥ 2 — топологическая сортировка не единственна. Если всегда ровно 1 — сортировка единственна.Это даёт время On+mn + mn+m.Алгоритм вариантнаосновеKahnвариант на основе KahnвариантнаосновеKahn
Вычислить invvv для всех вершин v входящаястепеньвходящая степеньвходящаястепень.Поместить в очередь Q все v с invvv = 0.i := 1.Пока Q не пуста:a. Если |Q| ≥ 2, вернуть "не единственна" (есть >1 возможный выбор).
b. v := единственный элемент Q; извлечь v.
c. orderiii := v; i := i + 1.
d. Для каждого ребра (v -> u) выполнить inuuu := inuuu - 1; если inuuu = 0, добавить u в Q.Если i = n+1 всевершиныобработанывсе вершины обработанывсевершиныобработаны, вернуть "единственна" и, при желании, order; иначе — граф содержит цикл поусловиюциклотсутствуетпо условию цикл отсутствуетпоусловиюциклотсутствует.
Корректность доказательстводоказательстводоказательство 1) Если когда‑то |Q| ≥ 2, то сортировка не единственна.
Пусть в некоторый момент источниками оставшихся вершин являются x и y x≠yx ≠ yx=y. Тогда оба варианта — сначала x потом y, и сначала y потом x — дадут корректные топологические упорядочения (поскольку ни одно из них не зависит от другого — нет ребра y->x и нет ребра x->y от оставшихся вершин), следовательно порядок не уникален.2) Если всегда |Q| = 1, то сортировка единственна.
Алгоритм Кана даёт некоторую топологическую сортировку order. Предположим существует другая сортировка order' ≠ order. Возьмём первую позицию t, где они различаются: order1..t−11..t-11..t−1 = order'1..t−11..t-11..t−1, а в позиции t разные вершины a = orderttt, b = order'ttt. Но после выбора первых t-1 вершин очередь источников однозначно определяется и по предположению всегда содержит ровно одну вершину, значит нельзя было выбрать и a, и b по-разному — противоречие. Следовательно порядок единственный.Эквивалентные характеризации единственности
Следующие условия эквивалентны для DAG G:
A) G имеет единственную топологическую сортировку.
B) При выполнении Kahn на каждом шаге ровно одна вершина имеет in = 0.
C) В некоторой азначитвединственнойа значит в единственнойазначитвединственной топологической сортировке v1, v2, ..., vn для всех i = 1..n-1 существует ребро vi -> v{i+1}. Тогда для любых i < j существует путь vi -> vj транзитивностьвдольпутитранзитивность вдоль путитранзитивностьвдольпути — то есть отношение достижимости задаёт линейный тотальныйтотальныйтотальный порядок на V.
Доказательство эквивалентности C с A/B:
Если существует i с отсутствующим ребром vi -> v{i+1}, то между vi и v{i+1} нет пути в одну сторону иначемеждунимивпорядкебылабыкакая−топромежуточнаявершинаиначе между ними в порядке была бы какая-то промежуточная вершинаиначемеждунимивпорядкебылабыкакая−топромежуточнаявершина, и значит эти две вершины сопоставимы, и можно их поменять местами в порядке — значит порядок не единственный. Поэтому при единственности ребро между каждым соседним парой обязательно есть.Наличие ребер между всеми соседями даёт путь между любой парой vi, vj черезпоследовательностьсоседнихреберчерез последовательность соседних реберчерезпоследовательностьсоседнихребер, значит любая топологическая сортировка должна сохранить этот порядок по достижимости, следовательно порядок единственен.Какие структуры графа дают единственность
Это ровно ориентированные цепи directedchainsdirected chainsdirectedchains покрытия всех вершин: DAG имеет единственную топологическую сортировку тогда и только тогда, когда он содержит ориентированный гамильтонов путь v1->v2->...->vn афактическиэтотпутьиестьединственныйпорядока фактически этот путь и есть единственный порядокафактическиэтотпутьиестьединственныйпорядок. Эквивалентно частично упорядоченное множество posetposetposet, заданное графом, является линейным totalorder,chaintotal order, chaintotalorder,chain.Примеры:Единственна: простой путь 1->2->3->...->n любыедополнительныеребра,согласованныесэтимпорядком,допустимы;главное—междулюбымидвумявершинамиболееранняядостижимакболеепозднейлюбые дополнительные ребра, согласованные с этим порядком, допустимы; главное — между любыми двумя вершинами более ранняя достижима к более позднейлюбыедополнительныеребра,согласованныесэтимпорядком,допустимы;главное—междулюбымидвумявершинамиболееранняядостижимакболеепоздней.Не единственна: два независимых пути, пара несравнимых вершин (u и v такие, что нет пути ни u->v ни v->u) — уже дают по крайней мере две топологические сортировки, переставляя эти вершины.
Сложность
Вычисление входящих степеней: On+mn + mn+m переборвсехрёберперебор всех рёберпереборвсехрёбер.Алгоритм Кана обрабатывает каждое ребро ровно один раз при уменьшении inuuu; операции с очередью — Onnn вставка/удалениевставка/удалениевставка/удаление. Итого On+mn + mn+m.Память: хранение списка смежности On+mn + mn+m и массивов in, order размером Onnn.Альтернативный эквивалентныйэквивалентныйэквивалентный способ проверки за On+mn + mn+m
Построить любую топологическую сортировку KahnилиDFSKahn или DFSKahnилиDFS.Проверить для каждой соседней пары в полученном порядке, есть ли ребро из предыдущей в следующую вершину. Если для какой‑то пары ребра нет — сортировка не единственна; если есть для всех — единственна.Этот способ корректен по аргументам выше и тоже On+mn + mn+m проверкуребрамеждусоседямиможноделатьзасуммарноO(n+m),еслихранитсясписоксмежности;длябыстройпроверкикаждогоконкретногоребраможно,например,пометитьсоседейпервойвершинывовременномхешепроверку ребра между соседями можно делать за суммарно O(n + m), если хранится список смежности; для быстрой проверки каждого конкретного ребра можно, например, пометить соседей первой вершины во временном хешепроверкуребрамеждусоседямиможноделатьзасуммарноO(n+m),еслихранитсясписоксмежности;длябыстройпроверкикаждогоконкретногоребраможно,например,пометитьсоседейпервойвершинывовременномхеше.
Итого
Простое и корректное решение: Kahn с проверкой |Q| == 1 на каждом шаге — On+mn + mn+m.Условие единственности: отношение достижимости в DAG — тотальный порядок; в терминах графа — граф содержит ориентированный Hamiltonian path, задающий единственный порядок (эквивалентно: в любой топологической сортировке для всех i есть ребро vi->v_{i+1}).