2.5. О порядковой функции

При таком способе действий некоторые дуги приходится просматривать более одного раза. Этого можно избежать, если просматривать дуги в определенном порядке, т.е. упорядочить их. Такой порядок можно задать, введя порядковую функцию на множестве А.

Определение. Порядковой функцией на орграфе без контуров называется функция, которая разбивает множество вершин графа на упорядоченные подмножества Е_i по правилу: вершина а_i  Е_i, если она достижима из а₀ не более чем за i шагов.

Множество Е_i обычно называют уровнями.

Для предыдущего примера порядковую функцию можно задать следующим образом (рис. 2.2).

Е₀ = {1}

Е₁ = {2, 4}

Е

1

Е₃ = {5}

Е₄ = {7}

3

4

Рис. 2.2

Упорядочив вершины по уровням, получим (рис. 2.3).

Рис. 2.3

Свойства упорядоченного графа:

1) все дуги расположены в направлении от начальной вершины к конечной; следовательно, при просмотре дуг антидерева в указанном порядке (см. шаг 4 б) ни одна вершина не проходится дважды, поэтому при смене дуг индексы предыдущих вершин не меняются, а перебор равен числу дуг антидерева;

2) вершины одного уровня не связаны дугами; следовательно, порядок просмотра вершин одного уровня безразличен.