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

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


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

Прямым транзитивным замыканием некоторой вершины хi – T+( хi )является объединение самой вершины хiс прямыми отображениями 1-го порядка, второго порядка и т. д., т. е.
T+( хi ) = хi Г+1 ( хi ) Г+2( хi ) ...
Многозначные отображения находятся до тех пор, пока в них добавляются новые вершины.
Так, для графа на рис. 3.1.
Г+1 ( х1 ) = { х2, х3 }, Г+2( х1 ) = { х3, х5 }, Г+3( х1 ) = { х3, х1 }, Г+4( х1 ) = {х2, х3}.
Отображение четвертого порядка содержит те же элементы, что и отображение 1-го порядка, следовательно, других элементов в последующих отображениях не появится. Транзитивное замыкание для вершины х1получается следующим образом:
T+( х1 ) = х1 { х2, х3 } { х3, х5 } { х3, х1 } = { х1, х2, х3, х5 }.
Проанализировав множество вершин, входящих в T+( хi ), можно сделать вывод: прямое транзитивное замыкание содержит вершины, в которые есть пути из вершины хi. Таким образом, можно дать второе определение T+( хi ).
Прямое транзитивное замыкание некоторой вершины хi T+( хi )– это множество вершин, достижимых из вершины хi, т. е. T ( хi ) = { хj | путь из хi в хj }.


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

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

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

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

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