Ациклический орграф - верно ли утверждение?

Подскажите - верно ли такое утверждение:

В ациклическом ориентированном графе можно пронумеровать вершины так, что для любого ребра номер начального узла будет меньше номера конечного узла.

Нутром чую - верно, а вот доказательства или ссылки на существование такового пока не сыскал.

А ещё лучше - если существует описание или программная реализация алгоритма такой нумерации узлов.

Сообщение отредактировано: Akina - 05.03.11, 08:23

Акина, в ФАКе лежат мои лекции по структурам данных, на стр.115-118 алгоритм правильной нумерации ациклического графа с доказательством корректности. Взят из книжки Липского "Комбинаторика для программистов".

Любой бесконтурный граф обладает следующим свойством: его вершины можно перенумеровать так, что любая дуга будет идти от вершины с меньшим номером к вершине с большим номером.
Такую нумерацию будем называть правильной.

Доказательством этого свойства будет служить алгоритм правильной нумерации.
Алгоритм основывается на следующем простом факте: в бесконтурном графе существует хотя бы одна вершина, в которую не заходит ни одна дуга (иначе бы в графе существовал контур).
Все такие вершины соберем в стек. Затем
1) вытолкнем из стека произвольную вершину;
2) присвоим ей номер 1;
3) удалим ее из графа вместе со всеми выходящими из нее дугами.
После операции удаления дуг могут появиться новые вершины, в которые не заходит ни одна дуга. Эти вершины помещаются в стек, затем из стека выталкивается произвольная вершина, ей присваивается следующий номер и т.д.
Понятно, что в результате получится правильная нумерация, так как любая вершина u получает номер в тот момент, когда оставшиеся еще незанумерованные вершины v (позже они получат большие номера) либо не соединены дугами с u, либо дуга идет в направлении (u→v).
Не так очевидно, почему все вершины получат номера:
если из стека удалили последнюю вершину, а в графе, получившемся после удаления этой вершины и выходящих из нее дуг, все вершины имеют заходящие в них дуги, то они уже никогда не попадут в стек и никогда не получат номера.
Дело в том, что при удалении из бесконтурного графа вершин и дуг всегда получается бесконтурный граф, а в нем существует хотя бы одна вершина без заходящих в нее дуг. Поэтому каждая вершина обязательно попадет в стек и получит соответствующий номер.
Поскольку из стека выталкивается произвольная вершина, то принцип стека не является обязательным и выбран только для удобства.
Списки инцидентности SLED: SLED[v] - указатель, к которому прицеплен список вершин u1, ..., uk таких, что существует направленная дуга v->ui, i=1...k.
АЛГОРИТМ {Правильная нумерация}
Данные: Бесконтурный орграф G=<V,E>, заданный списками инцидентности SLED[v], v из V.
Результаты: Для каждой вершины v новый номер NN[v] такой, что номера NN[v] являются правильной нумерацией графа G.
1 begin
{INP[v] – число дуг, заходящих в вершину v}
2 for v из V do INP[v]:= 0;
3 for u из V do
4 for v из SLED[u] do
{находим все вершины v, для которых (u→v)}
5 INP[v]:= INP[v]+1;
6 СТЕК:= 0;
7 for v из V do
8 if INP[v]=0 then СТЕК из v;
9 num:= 0; {текущий номер}
10 while СТЕК <> 0 do
11 begin
12 u из СТЕК;
13 num:= num+1;
14 NN[u]:= num;
15 for v из SLED[u] do
16 begin
17 INP[v]:= INP[v]–1;
18 if INP[v]=0 then СТЕК из v;
19 end;
20 end;
21 end.
Все дуги графа анализируются два раза: в цикле 3–5 для подсчета числа заходящих дуг INP[v], в цикле 10–20, где удаление дуг из графа заменено уменьшением чисел INP[v].
Таким образом, вычислительная сложность алгоритма пропорциональна числу дуг, т.е. равна О(m) шагов.

Добавлено 05.03.11, 09:07
Прожки уже нет...

Сообщение отредактировано: Swetlana - 05.03.11, 11:11

Отлично, спасибо.
Теперь осталось реализовать всё это на SQL... придётся CTE, видимо...

топологическая сортировка разве эту задачу не решает?

MBo
Собсно вся задача выглядит так: есть SQL-таблица, хранящая такой граф в виде (NodeID - ParentID - DataFields). И нужно получить все строки таблицы, сортированные именно в указанном порядке. Соответственно в рамках хранимой процедуры нужно организовать расчёт ещё одного поля - номера, по которому будет выполнена сортировка (номер нужен не только для сортировки - он потребуется в дальнейшем).
Теперь я знаю, что это можно сделать, не боясь, что попадётся тупиковая ситуация. А программная реализация - дело десятое. Попробуем и так, и эдак...

Сообщение отредактировано: Akina - 05.03.11, 09:44