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

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


Нахождение множества вершин, входящих в путь

Если необходимо узнать о вершинах графа, входящих в эти пути, то следует вспомнить определения прямого и обратного транзитивных замыканий. Так как T+(xi) – это множество вершин, в которые есть пути из вершины xi, а T–(хj) – множество вершин, из которых есть пути в xj , то T+(xi) T–(xj)– множество вершин, каждая из которых принадлежит, по крайней мере, одному пути, идущему от xi к xj . Эти вершины называются существенными или неотъемлемыми относительно двух концевых вершин xi и xj . Все остальные вершины графа называются несущественными или избыточными, поскольку их удаление не влияет на пути от xi к xj .
Рис. 4.2. Орграф
Так для графа на рис. 4.2 нахождение вершин, входящих в путь, например из вершины х2 в вершину х4 , сводится к нахождению Т+( х2) ={ х2, х3, х4, х5, х6}, Т-( х4) ={ х1, х2, х3, х4, х5}, и их пересечения T+(х2) T–(х4) ={ х2, х3, х4, х5}.


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

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

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

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

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