Page 13 - 4387

Крок 3. Оскільки існують елементи a =1, то
i,j
переходимо до кроку 4. Т (v )
-
3
Крок 4. d=d+1=1, i={1, 4}, j=i={1, 4}, v 1
1
-
-
Т (v ) →d, Т (v ) →d. v 3
2
3 1
3 4
Крок 5. Переглядаємо 1-й та 4-й стовпчики v 0
3
4
матриці А: a =1, a =1, a =1. Переходимо до v 1
5,4
6,1
5,1
5
кроку 3. v 2
v
2
Крок 3. Оскільки існують елементи a =1, то 6
i,j
переходимо до кроку 4. Рисунок 1.4.
-
-
Крок 4. d=d+1=2. i={5, 6}, j=i={5, 6}, Т (v ) →d, Т (v ) →d.
3 6
3 5
Крок 5. Переглядаємо 5-й та 6 стовпчики матриці А: a =1,
2,5
a =1. Переходимо до кроку 3.
6,5
Крок 3. Оскільки існують елементи a =1, то переходимо до
i,j
кроку 4.

-
Крок 4. d=d+1=3. Елемент вектора Т (v ) уже заповнений,
3 6
-
-
тому i=2, j=i=2, Т (v ) →d. Оскільки усі елементи вектора Т (v )
3
3 2
заповнені, то процес формування зворотного транзитивного
замикання завершується.

-
Таким чином, у векторі Т (v ) стоять числа рівні довжинам
3
шляхів від відповідних вершин до вершини v . Отже, дані
3
вершини входять у зворотне транзитивне замикання вершини v –
3
-
Т (v )={v , v , v , v , v , v }.
2
3
3
1
4
6
5
1.3 Порядок виконання роботи
Варіант № 1

1. Знайти прямі багатозначні відображення для усіх

вершин графа, зображеного на рис. 1.5 а.

12