Многозначные отображения и транзитивные замыкания

Многозначные отображения

Прямые отображения

Прямым отображением 1-го порядка вершины хi является множество таких вершин графа, для которых существует дуга (хi, xj), т. е $$Г^{1}( х_{i} ) = \{ x_{j} : \exists \ дуга (х_{i}, x_{j}) \in A\}$$ для графа G = (X, A), где X ={ хi }, i =1, 2, ..., n – множество вершин, а A = {ai}, i = = 1, 2, ..., m – множество дуг.

Прямое отображение 2-го порядка вершины х_i – это прямое отображение от прямого отображения 1-го порядка, т. е. Г+2( хi ) = Г+( Г+1 ( хi ) ).

Аналогично можно записать для прямого отображения 3-го и т. д. n -го порядка.

Г+3(xi)= Г+(Г+2(xi))= Г+(Г+(Г+1(xi)))

...

Г+n(xi)=Г+(Г+(n-1)(xi)).

Прямые многозначные отображения для графа на находятся следующим образом:

Г+1(x1)=(x2,x3),

Г+2(x1)=Г+(Г+1(x1))=Г+(x2,x3)=(x3,x5),

Г+3(x1)=Г+(Г+2(x1))=Г+(x3,x5)=(x3,x1) и т. д.

Обратные отображения

Обратным отображением 1-го порядка для вершины хi является множество элементов xj таких, что существует дуга (xj, хi), принадлежащая множеству дуг графа, т. е. $$Г^{-1}(х_{i} ) = \{ x_{j} : \exists \ дуга (х_{j}, х_{i}) \in А \}$$.

Обратные отображения 2-го, 3-го и т. д. n -го порядка определяются следующим образом:

Г-2(xi)= Г-(Г-1(xi)),

Г-3(xi)= Г-(Г-2(xi)),

...

Г-n(xi)= Г-(Г(n-1)(xi)).

Для графа на обратные многозначные отображения вершины х1 находятся следующим образом:

Г-1(x1)=x5,

Г-2(x1)= Г-(Г-1(x1))=Г-(x5)= x2,x4,

Г-3(x1)= Г-(Г-2(x1))=Г-(x2x4)= x1,

Г-4(x1)= Г-(Г-3(x1))=Г-(x1)= x5 и т.д.

П р и м е ч а н и я:

1. Когда отображение действует не на одну вершину, а на множество вершин Хq = { х1, х2, ..., хq }, то под Г(Хq) понимают объединение

$$Г(х_{1}) \cup Г(х_{2}) \cup \dots \cup Г(х_{q})$$.

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

Транзитивные замыкания

Прямое транзитивное замыкание

Прямым транзитивным замыканием некоторой вершины хi – T+( хi ) является объединение самой вершины хi с прямыми отображениями 1-го порядка, второго порядка и т. д., т. е.

$$T^{+}( х_{i} ) = х_{i} \cup Г^{+1} ( х_{i} ) \cup Г^{+2}( х_{i} ) \cup ..$$.

Многозначные отображения находятся до тех пор, пока в них добавляются новые вершины.

Так, для графа на .

Г+1 ( х1 ) = { х2, х3 }, Г+2( х1 ) = { х3, х5 }, Г+3( х1 ) = { х3, х1 }, Г+4( х1 ) = { х2, х3 }.

Отображение четвертого порядка содержит те же элементы, что и отображение 1-го порядка, следовательно, других элементов в последующих отображениях не появится. Транзитивное замыкание для вершины х1 получается следующим образом:

$$T^{+}( х_{1} ) = х_{1} \cup \{ х_{2}, х_{3} \} \cup \{ х_{3}, х_{5} \} \cup \{ х_{3}, х_{1} \} = \{ х_{1}, х_{2}, х_{3}, х_{5} \}$$.

Проанализировав множество вершин, входящих в T+( хi ), можно сделать вывод: прямое транзитивное замыкание содержит вершины, в которые есть пути из вершины хi. Таким образом, можно дать второе определение T+( хi ).

Прямое транзитивное замыкание некоторой вершины хi T+( хi ) – это множество вершин, достижимых из вершины хi, т. е. $$T ( х_{i} ) = \{ х_{j} | \exists \ путь \ из \ х_{i} в \ х_{j} \}$$ .

Обратное транзитивное замыкание

Обратным транзитивным замыканием некоторой вершины хi –T-( хi ) является объединение этой вершины с обратными отображениями 1-го, 2-го и т. д. n -го порядка, т. е.

$$T^{-}( х_{i} ) = х_{i} \cup Г^{-1}(х_{i} ) \cup Г^{-2}(х_{i} ) \cup ..$$.

Иначе, обратное транзитивное замыкание для некоторой вершины хi – T-( хi ) – это множество вершин, из которых достижима вершина $$х_{i}, т. е. T^{-}( х_{i} ) = \{ x_{j} | \exists \ путь \ из \ x_{j} \ в \ х_{i} \}$$.

Рассмотрим построение обратного транзитивного замыкания для графа на .

$$Г^{-1}(х_{1}) = \{ х_{5} \} ,Г^{-2}(х_{1}) = \{ х_{2}, х_{4} \} ,Г^{-3}(х_{1}) = \{ х_{1} \} ,Г^{-4} (х_{1}) = \{ х_{5} \} ,T^{-}(х_{1}) = х_{1} \cup \{ х_{5} \} \cup \{ х_{2}, х_{4} \} \cup \{ х_{1} \} \cup \{ х_{5} \} = \{ х_{1}, х_{2}, х_{4}, х_{5}\}$$.

Нахождение транзитивных замыканий по матрице смежности

Рассмотрим метод нахождения прямого транзитивного замыкания по матрице смежности, показанной на ,а для вершины ,б. На 1-м шаге итерации заносим 0 в столбец Т+ для элемента х2 и просматриваем 2-ю строку матрицы. Находим, что элементы a22=1 и a25=1. Заносим 1 в 5-ю клетку Т+. 2-я клетка уже занята нулем, поэтому 1 не заносим. 2-й шаг начинается просмотром 5-й строки матрицы смежности, соответствующий вершине х5 графа. Находим, что элементы a51=1 и a54=1, т. е. из вершины х5 имеются дуги в вершины х1 и х4 или иначе из вершины х2 имеются пути длиной 2 в вершины х1 и х4. Длину пути 2 заносим в 1-ю и 4-ю клетки столбца T+(х2). На 3-м шаге анализируются 1-я и 4-я строки матрицы смежности А. Находим элементы a12=1, a13=1, a43=1. В соответствующие свободные клетки заносим значения

Это возможно сделать только для вершины х3, так как вторая клетка уже занята. Анализ 3-й строки матрицы на 4-м шаге показывает, что из вершины х3 нет исходящих дуг, следовательно, процесс формирования прямого транзитивного замыкания завершен.

Таким образом, в столбце ,б. В столбце T+( х2 ) отмечены все вершины, достижимые из вершины х2, следовательно, они входят в T+( х2 ).

T+( х2 ) = { х1, х2, х3, х4, х5 }.

Во втором столбце показано построение прямого транзитивного замыкания вершины х1 – T+( х1 ).

T+( х1 ) = { х1, х2, х3, х4, х5 }.

Нахождение обратного транзитивного замыкания по матрице смежности показано на ,в. Рассмотрим нахождение обратного транзитивного замыкания вершины х3 – T-( х3 ), которое начинается с занесения 0 в 3-ю клетку строки T-( х3 ). На 1-м шаге алгоритма, помеченного стрелкой с цифрой 1, просматриваем 3-й столбец матрицы А. Определяем элементы равные 1, т. е. a13=1 и a43=1. Следовательно, в графе из вершин х1 и х4 есть дуги в вершину х3. Заносим 1 в 1-ю и 4-ю клетки T-(х3). На втором шаге просматриваем 1-й и 4-й столбцы матрицы A. Находим a51=1, a61=1, a54=1 и проставляем 2 (так как длина пути от этих вершин до вершины х3 равна 2) в свободные клетки T-(х3), т. е. в 5-ю и 6-ю клетки. 3-й шаг заключается в просмотре 5-го и 6-го столбцов матрицы A. Элементы a25=1, a65=1, a66=1 позволяют поставить 3 во 2-ю клетку строки T-( х3 ). 4-й шаг просмотра 2-го столбца дает элементы a12 = 1 и a22 = 1, уже вошедшие в T-(х3). Итак, сформировано обратное транзитивное замыкание для вершины х3.

T-( х3 ) = { х1, х2, х3, х4, х5, х6 }.

Числа, стоящие в клетках T-( х3 ), показывают длину кратчайшего пути от соответствующих вершин до вершины х₃.

Во второй строке показано формирование обратного транзитивного замыкания вершины х1.

T-( х1 ) = { х1, х2, х5, х6 }.