Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Обратное соответствие

Читайте также:
  1. I. Найди соответствие
  2. Ww. Установите соответствие
  3. ГЛАВА 3. СООТВЕТСТВИЕ СКОРОСТИ И ПЕРЕДАЧИ
  4. Для прекращения начавшегося заноса следует сделать действие обратное тому действию, которое привело к заносу!
  5. Ж.1 Рекомендации по проверке состояния оборудования на соответствие требованиям охраны труда и промышленной безопасности. Общая часть
  6. Изъян государства – это его неспособность обеспечить аллокационную эффективность и соответствие политики распределения принятым в обществе представлениям о справедливости.
  7. На соответствие

Поскольку представляет собой множество таких вершин , для которых в графе G существует дуга i, хj), то через естественно обозначить множество вершин хk, для которых в G существует дуга k, хi). Отношение принято называть обратным соответствием. Для графа, изображенного на рис (а), имеем

и т. д.

Для неориентированного графа для всех .

Когда отображение Г действует не на одну вершину, а на множество вершин , то под ) понимают объединение

-

т. е. является множеством таких вершин , что для каждой из них существует дуга i, хj) в G, где .

Пример.

Для графа, приведенного на рис. (а), и .

 

Отображение Г(Г(хi)) записывается как Г2i). Аналогично «тройное» отображение Г(Г(Г(хi))) записывается как Г3i) и т. д.

Пример.

Для графа, показанного на рис. (а), имеем:

Г21) = Г(Г(x1)) = Г({х2, х5}) = {x1, x3, x4}

Г31) = Г(Г2(x1)) = Г({x1, x3, x4}) = {x1, x2, x5} и т. д.

 

Аналогично понимаются обозначения Г-2 (xi), Г-3(xi) и т. д


Дата добавления: 2015-07-07; просмотров: 88 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Граф, вершина, ребро| Граф со взвешенными дугами

mybiblioteka.su - 2015-2021 год. (0.01 сек.)