Разработка компиляторов



   Здесь низкие цены на консульскую легализацию документов        

Глубинное остовное дерево


Нумерацией называется взаимно однозначное отображение множества вершин графа на отрезок натурального ряда [1..|V|]. Для заданной нумерации # дуга (v, w) - прямая, если #(v)<#(w) и обратная в противном случае.

Остовное дерево - это дерево, содержащее все вершины графа и некоторые его дуги. Глубинное остовное дерево - это остовное дерево, полученное при обходе в глубину. Данный обход начинается в вершине start и заключается в последовательном включении вершин и ребер графа в дерево, если их еще там нет. При этом следующий сын вершины посещается лишь тогда, когда посещены все вершины, достижимые из предыдущего сына вершины.

Существует четыре типа дуг графа по отношению к данному глубинному остовному дереву: деревянные, прямые, обратные и поперечные. Следует отличать просто обратные дуги в графе (для определения которых было использовано отношение обязательного предшествования) и обратные дуги по отношению к глубинному остовному дереву.

  • К деревянным относятся те дуги, которые входят в состав остовного дерева.
  • К прямым дугам относятся те, чей конец достижим из начала в остовном дереве.
  • К обратным дугам относятся те, чье начало достижимо из конца в остовном дереве.
  • К поперечным дугам относятся все остальные.

Легко видеть, что при построении остовного дерева возникает порядок, в котором вершины графа включаются в рассмотрение. Нумерация, которая описывает этот порядок, называется прямой ( Pre ).

Аналогично, существует порядок, в котором вершины графа исключаются из рассмотрения. Нумерация, описывающая порядок, обратный к нему, называется обратной (Post ).




Содержание  Назад  Вперед