3. Порядковая функция орграфа без контуров

Рассмотрим орграф D(V, X) , не содержащий контуров, и определим множества

Граф D (V, X) не содержащий контуров – бесконтурный орграф.

Определим для него множества:

V ₀ = {u Î V | D (u) = Æ};

V

(*)

V₂ = {u Î V \ (V₀ È V₁) | D (u) Í V₀V₁};

…………………………………….

V_r = {u Î V \ È V_k | D (u) Í V_k},

Где D(v) – множество образов, r – наименьшее число, такое, что V \ È V_k = Æ (k = 0, 1,…, r).

V₀, V₁, …, V_r – уровни графа.

Уровни образуют разбиение множества вершин V, то есть

È V_k = V (k = 0,1,…,r).

Справедливо утверждение:

Пусть D(V, X) – орграф, r  0, V₀, …, V_r – непустые множества, удовлетворяющие (*), такие, что È V_k = V (k = 0,1,…, r). Тогда D – орграф без контуров.

Функция q (u), определенная на множестве вершин V орграфа без контуров D(V, X) и ставящая в соответствие любой вершине v  V номер уровня, которому она принадлежит, называется порядковой функцией орграфа D (V, X).

Пример:

Разбить граф D (V, X) на уровни и изобразить в уровневом представлении.

1) Найдём вершины, не имеющие образов и присвоим номер уровня 0:

V₀ = {u  V | D (u) = } = {u₄, u₆}. Порядковые функции для v₄ и v₆ равны

q (u₄) = 0, q (u₆) = 0.

2) Найдём вершины, образами которых являются u₄ и u₆:

V₁ = {u V \ V₀ | D(u) Í {u₄, u₆}} = {u₁, u₅}. q (u₁) = 1, q (u₅) = 1.

3) V₂ = {u V \ V₀  D (u) Í {u₄, u₆, u₁, u₅}} = {u₃}, q (u₃) = 2.

4) Тогда V₃ = {u₂}, q (u₂) = 3.

Итак, получили множества V₀, V₁, V₂ и V₃ такие , что их взаимное пересечение пусто, а объединение есть множество вершин V графа . Следовательно граф - без контуров.

Рассмотрим алгоритм выделения уровней орграфа D(V, X) без контуров, использующий задание графа матрицей смежности. Этот алгоритм легко реализуется на ЭВМ:

Шаг 1. Составим матрицу смежности. Образуем под этой матрицей строку ₀, в i – том месте которой укажем число единиц в i – той строке матрицы. Уровень V₀ образуют вершины, которым в строке ₀ соответствует 0. если V = V₀, то задача решена и V₀ – единственный уровень орграфа D. В противном случае переходим к шагу 2.

Шаг 2. Образуем под строкой ₀ строку ₁, ставя под каждым нулем строки символ , а на любом другом i – том месте – число единиц в i – ой строке матрицы, не учитывая единицы в столбцах над символами  в строке ₁. Уровень V₁ образуют вершины, которым в строке ₁ соответствует число 0. Полагаем j = 1.

Шаг 3. Пусть при некотором j  1уже построены строки ₀ , ₁,…, _j , по которым получены множества V₀, …, V_j . Если строка _j состоит из нулей и символов  , то задача решена и при r = j V₀, …, V_r – уровни орграфа. В противном случае переходим к шагу 4.

Шаг 4. Образуем под строкой _j строку _j+1, ставя под каждым нулем и символом  символ , а на любом другом i – том месте – число единиц в i – ой строке матрицы, не учитывая единицы в столбцах над символами  в строке _j+1. Уровень V_j+1 образуют вершины, которым в строке _j+1 соответствует число 0. Присваиваем j : = j + 1 и переходим к шагу 3.

Решим предыдущую задачу с помощью матрицы смежности и описанного алгоритма.

Согласно полученным строкам l_j:

V₀ = {u₄, u₆},

V₁ = {u₁, u₅},

V₂ = {u₃},

V₃ = {u₂}.

Следовательно, для данного графа количество уровней – четыре. Изобразим граф в уровневом представлении:

V₃ V₂ V₁ V₀

Наряду с нахождением уровней орграфа без контуров этот алгоритм позволяет проверить наличие контуров у произвольного графа. Справедливо утверждение:

Орграф D(V, X) содержит хотя бы один контур тогда и только тогда, когда в результате применения алгоритма к графу D появляется строка _j без нулей.

Такой граф не представим в виде уровней.

Рассмотрим пример. Проверить наличие контуров в орграфе D(V, X), заданном матрицей смежности:

Применяя алгоритм, получим:

Поскольку в строке ₃ нет нулей, то орграф содержит хотя бы один контур.