Разработка компиляторов
Глубинное остовное дерево
Нумерацией называется взаимно однозначное отображение множества вершин графа на отрезок натурального ряда [1..|V|]. Для заданной нумерации # дуга (v, w) - прямая, если #(v)<#(w) и обратная в противном случае.
Остовное дерево - это дерево, содержащее все вершины графа и некоторые его дуги. Глубинное остовное дерево - это остовное дерево, полученное при обходе в глубину. Данный обход начинается в вершине start и заключается в последовательном включении вершин и ребер графа в дерево, если их еще там нет. При этом следующий сын вершины посещается лишь тогда, когда посещены все вершины, достижимые из предыдущего сына вершины.
Существует четыре типа дуг графа по отношению к данному глубинному остовному дереву: деревянные, прямые, обратные и поперечные. Следует отличать просто обратные дуги в графе (для определения которых было использовано отношение обязательного предшествования) и обратные дуги по отношению к глубинному остовному дереву.
- К деревянным относятся те дуги, которые входят в состав остовного дерева.
- К прямым дугам относятся те, чей конец достижим из начала в остовном дереве.
- К обратным дугам относятся те, чье начало достижимо из конца в остовном дереве.
- К поперечным дугам относятся все остальные.
Легко видеть, что при построении остовного дерева возникает порядок, в котором вершины графа включаются в рассмотрение. Нумерация, которая описывает этот порядок, называется прямой ( Pre ).
Аналогично, существует порядок, в котором вершины графа исключаются из рассмотрения. Нумерация, описывающая порядок, обратный к нему, называется обратной (Post ).
