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

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


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

Обратным отображением 1-го порядка для вершины хiявляется множество элементов xjтаких, что существует дуга(xj, хi), принадлежащая множеству дуг графа, т. е. Г-1(хi ) = { xj : дуга (хj, хi) А }.
Обратные отображения 2-го, 3-го и т. д. n-го порядка определяются следующим образом:
Г-2(xi)= Г-(Г-1(xi)),
Г-3(xi)= Г-(Г-2(xi)),
...
Г-n(xi)= Г-(Г(n-1)(xi)).
Для графа на рис. 3.1 обратные многозначные отображения вершины х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) Г(х2) ... Г(хq).
2. Многозначное отображение для неориентированного графа строится, если представить каждое ребро двумя противоположно направленными дугами (рис. 3.2).

Рис. 3.2. Граф: а – неориентированный; б – тождественный ему ориентированный


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

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

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

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

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