18. Ориентированные графы, источники и стоки, топологическая сортировка, алгоритм Демукрона.

Определение. Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Определение. Ориентированные графы - графы с ориентированными (имеющими направление) ребрами. У таких графов каждое ребро выходит из его начальной в его конечную вершину и называется дугой. Всякая вершина, в которую не входит ни одна дуга, называется источником, а вершина, из которой нет выходящих дуг – стоком.

Топологической сортировкой ориентированногоn-вершинного графа называется процесс, в результате которого каждой вершине приписывается номер из множества {1, 2, …,n} так, чтобы любая дуга была направлена от вершины с меньшим номером к вершине с бóльшим номером. Известно, что топологическая сортировка возможна лишь в том случае, если граф не содержит ориентированных циклов.

Алгоритм Демукрона для топологической сортировки графа.В этом алгоритме циклически повторяется одно и то же действие: в текущем графе находят источники, нумеруют их минимальными числами из текущего множества и затем удаляют их вместе с выходящими из них дугами. В начальный момент текущий граф – это исходный граф, а текущее множество – это множество {1, 2, …,n}. Алгоритм завершает работу, как только все вершины исходного графа окажутся пронумерованными.