Топологическая сортировка — упорядочивание вершин ациклического ориентированного графа согласно частичному порядку, заданному рёбрами орграфа на множестве его вершин.
Например, для графа:
существует несколько согласованных последовательностей его вершин, которые могут быть получены при помощи топологической сортировки, в частности:
В последовательности могут быть переставлены любые две стоящие рядом вершины, которые не входят в отношение частичного порядка .
Топологическая сортировка широко применяется в различных отраслях например, с её помощью можно построить последовательность прохождения учебных курсов студентами, последовательность установки программ при помощи пакетного менеджера, последовательность сборки исходных текстов программ по данным сборочных файлов, можно построить список отображения объектов в изометрической проекции зная парные порядковые отношения между объектами (какой из двух объектов должен быть прорисован раньше).
Один из первых алгоритмов, и наиболее приспособленный к исполнению вручную разработан Артуром Каном в 1962 году.
Пусть дан ациклический ориентированный простой граф . Через обозначим множество таких вершин , что . То есть — множество всех вершин, из которых есть дуга в вершину . Пусть — искомая последовательность вершин.
пока
выбрать любую вершину такую, что и
удалить из всех
Наличие хотя бы одного цикла в графе приведёт к тому, что на определённой итерации цикла не удастся выбрать новую вершину .
Например, если задан граф:
,
алгоритм выполнится следующим образом:
шаг
0
1
2
3
4
5
На втором шаге вместо может быть выбрана вершина , поскольку порядок между и не задан.
С использованием вычислительной техники топологическую сортировку можно выполнить за времени и памяти, если обойти все вершины, используя поиск в глубину, и выводить вершины в момент выхода из неё — алгоритм разработан Робертом Тарьяном в 1976 году.
Изначально все вершины помечаются как белые, для каждой вершины осуществляется шаг алгоритма:
если вершина чёрная, ничего делать не надо,
если вершина серая — найден цикл, топологическая сортировка невозможна,
если вершина белая, то:
красится в серый,
применяется шаг алгоритма для всех вершин, в которые можно попасть из текущей,
вершина красится в чёрный и помещается в начало окончательного списка.
Например, на графе:
с порядком обхода алгоритм отрабатывает следующим образом:
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К.Глава 22.4. Топологическая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 632—635. — ISBN 5-8459-0857-4.
Просто́е число́ — натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число является простым, если оно отлично от и делится без остатка только на и на само .
Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин.
Прямое произведение — множество, элементами которого являются все возможные упорядоченные пары элементов заданных двух непустых исходных множеств. Предполагается, что впервые «декартово» произведение двух множеств ввёл Георг Кантор.
Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
как и геометрия, обладает наглядностью;
как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
не имеет громоздкого математического аппарата ;
имеет выраженный прикладной характер.
Ориентированный граф — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Граф, ни одному ребру которого не присвоено направление, называется неориентированным графом или неорграфом.
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре.
Дерево — связный ациклический граф. Связность означает наличие маршрута между любой парой вершин, ацикличность — отсутствие циклов. Отсюда, в частности, следует, что число рёбер в дереве на единицу меньше числа вершин, а между любыми парами вершин имеется один и только один путь.
Алгори́тм Де́йкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации OSPF и IS-IS.
Поиск в глубину — один из методов обхода графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.
Поиск в ширину — один из методов обхода графа. Пусть задан граф и выделена исходная вершина . Алгоритм поиска в ширину систематически обходит все ребра для «открытия» всех вершин, достижимых из , вычисляя при этом расстояние от до каждой достижимой из вершины. Алгоритм работает как для ориентированных, так и для неориентированных графов.
Матрица достижимостипростого ориентированного графа — бинарная матрица замыкания по транзитивности отношения . Таким образом, в матрице достижимости хранится информация о существовании путей между вершинами орграфа.
Алгоритм Эдмондса — Карпа решает задачу нахождения максимального потока в транспортной сети. Алгоритм представляет собой частный случай метода Форда — Фалкерсона и работает за время в графе . Впервые был опубликован в 1970 году советским учёным Е. А. Диницом. Позже, в 1972 году, был независимо открыт Эдмондсом и Карпом.
Матрица смежности — один из способов представления графа в виде матрицы.
Зада́ча Ште́йнера о минима́льном де́реве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости. Задача получила своё название в честь Якоба Штейнера (1796—1863).
ACE — набор программных средств, реализующих шифрование в режиме схемы шифрования с открытым ключом, а также в режиме цифровой подписи. Соответствующие названия этих режимов — «ACE Encrypt» и «ACE Sign». Схемы являются вариантами реализации схем Крамера-Шоупа. Внесённые изменения нацелены на достижение наилучшего баланса между производительностью и безопасностью всей системы шифрования.
Граф зависи́мостей — ориентированный граф, отображающий соотношение множества элементов некоторой совокупности в соответствии с выбранным транзитивным отношением над ней.
Теорема Визинга — утверждение теории графов, согласно которому рёбра любого простого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин графа. Поскольку цветов достаточно всегда, все неориентированные графы можно разбить на два класса — графы «первого класса», для которых цветов достаточно, и «второго класса», для которых необходимо цветов.
Задача о самом длинном пути — это задача поиска простого пути максимальной длины в заданном графе. Путь называется простым, если в нём нет повторных вершин. Длина пути может быть измерена либо числом рёбер, либо суммой весов его рёбер. В отличие от задачи кратчайшего пути, которая может быть решена за полиномиальное время на графах без циклов с отрицательным весом, задача нахождения самого длинного пути является NP-трудной и не может быть решена за полиномиальное время для произвольных графов, если только не P = NP. Принадлежность более тяжелому классу сложности также означает, что задачу трудно аппроксимировать. Однако задача решается за линейное время на ориентированных ациклических графах, которые имеют важное применение в задачах нахождения критического пути в задачах планирования.
Биполярная ориентация или st-ориентация неориентированного графа — это назначение ориентации каждому ребру (ориентации), что превращает граф в направленный ациклический граф с единственным источником s и единственном стоком t, а st-нумерация графа — это топологическая сортировка полученного ориентированного ациклического графа.
Алгоритм Суурбалле — это алгоритм нахождения двух непересекающихся путей в ориентированном графе с неотрицательными весами, так что оба пути связывают ту же самую пару вершин и имеют минимальную общую длину.
Эта страница основана на статье Википедии. Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия. Изображения, видео и звуки доступны по их собственным лицензиям.