double arrow

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


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

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

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

V0 = {u О V | D (u) = Ж};

(*)
V1 = {u О V \ V0 | D (u) Н V0};

V2 = {u О V \ (V0 И V1) | D (u) Н V0ÈV1};

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

Vr = {u О V \ И Vk | D (u) Н ÈVk},

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

V0, V1, …, Vr – уровни графа.

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

И Vk = V (k = 0,1,…,r).

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

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

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

Пример:

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

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

V0 = {u Î V | D (u) = Æ} = {u4, u6}. Порядковые функции для v4 и v6 равны

q (u4) = 0, q (u6) = 0.

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




V1 = {u ÎV \ V0 | D(u) Н {u4, u6}} = {u1, u5}. q (u1) = 1, q (u5) = 1.

3) V2 = {u ÎV \ V0 È D (u) Н {u4, u6, u1, u5}} = {u3}, q (u3) = 2.

4) Тогда V3 = {u2}, q (u2) = 3.

Итак, получили множества V0, V1, V2 и V3 такие , что их взаимное пересечение пусто, а объединение есть множество вершин V графа . Следовательно граф - без контуров.

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

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

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

Шаг 3. Пусть при некотором j ³ 1уже построены строки l0 , l1,…, lj , по которым получены множества V0, …, Vj . Если строка lj состоит из нулей и символов ´ , то задача решена и при r = j V0, …, Vr – уровни орграфа. В противном случае переходим к шагу 4.

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



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

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

V0 = {u4, u6},

V1 = {u1, u5},

V2 = {u3},

V3 = {u2}.

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

 
 


V3 V2 V1 V0

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

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

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

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

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

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







Сейчас читают про: