Конспект лекций по предмету "Теория графов"

Узнать цену работы по вашей теме


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

Рассмотрим метод нахождения прямого транзитивного замыкания по матрице смежности, показанной на рис. 3.3,а для вершины х2графа, изображенного на рис. 3.3,б. На 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. Построение прямого (а) и обратного (в) транзитивных замыканий для графа (б)
Это возможно сделать только для вершины х3, так как вторая клетка уже занята. Анализ 3-й строки матрицы на 4-м шаге показывает, что из вершины х3нет исходящих дуг, следовательно, процесс формирования прямого транзитивного замыкания завершен.
Таким образом, в столбце T+(х2)стоят числа равные длине пути от вершины х2 к соответствующим вершинам графа. Путь от х2 к х3равный 3 показан штриховой линией на рис. 3.3,б. В столбце T+(х2) отмечены все вершины, достижимые из вершины х2, следовательно, они входят в T+(х2).
T+( х2 ) = { х1, х2, х3, х4, х5 }.
Во втором столбце показано построение прямого транзитивного замыкания вершины х1 – T+(х1).
T+( х1 ) = { х1, х2, х3, х4, х5 }.
Нахождение обратного транзитивного замыкания по матрице смежности показано на рис. 3.1,в. Рассмотрим нахождение обратного транзитивного замыкания вершины х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 ), показывают длину кратчайшего пути от соответствующих вершин до вершины х3.
Во второй строке показано формирование обратного транзитивного замыкания вершины х1.
T-( х1 ) = { х1, х2, х5, х6 }.


Не сдавайте скачаную работу преподавателю!
Данный конспект лекций Вы можете использовать для создания шпаргалок и подготовки к экзаменам.

Доработать Узнать цену работы по вашей теме
Поделись с друзьями, за репост + 100 мильонов к студенческой карме:

Пишем конспект самостоятельно:
! Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать.

Другие популярные конспекты:

Конспект Основные проблемы и этапы развития средневековой философии
Конспект Проблема познаваемости мира. Гносеологический оптимизм, скептицизм, агностицизм. Взаимосвязь субъекта и объекта познания
Конспект Понятие финансовой устойчивости организации
Конспект Внутренняя политика первых Романовых.
Конспект ПРОБЛЕМЫ КВАЛИФИКАЦИИ ПРЕСТУПЛЕНИЙ
Конспект Понятие мировоззрения, его уровни и структура. Исторические типы мировоззрения
Конспект Синтагматические, парадигматические и иерархические отношения в языке
Конспект Тема 1.2. Плоская система сходящихся сил. Определение равнодействующей геометрическим способом 13
Конспект Происхождение человека. Основные концепции антропосоциогенеза. Антропогенез и культурогенез.
Конспект Общая характеристика процессов сбора, передачи, обработки и накопления информации