Способи задання бінарних відношень

Теоретичні основи

§ 4. БІНАРНІ ВІДНОШЕННЯ

Бінарне відношення R у множині М - це підмножина його квадрата: , де .

Елементи перебувають у відношенні R, якщо , - кортеж.

1. Матриця суміжності – це матриця ,

Приклад.Задано блок-схему ЕОМ, запропоновану фон Нейманом, що складається із множини пристроїв М={a,b,c,d,e}, де a – пристрій введення, b – процесор (арифметичний пристрій), c – пристрій керування, d – запам'ятовувальний пристрій, e – пристрій виводу. Якщо із пристрою m_i надходить інформація в пристрій т_j ,то ці пристрої перебувають у відношенні R, під яким розуміється інформаційний обмін між цими пристроями. Задати відношення R у вигляді матриці суміжності.

□ Матриця суміжності має вигляд

Множина отриманих кортежів визначає відношення

R = {(a,b),(a,c),(a,d ),(b,c),(b,d ),(b,e),(c,a),(c,b),(c,d ),(c,e),(d,b),(d,c),(d,e), (e,c)}.

Відношення R підмножина множини М, тобто , що погоджується з визначенням бінарного відношення.

2. Граф - сукупність множини М з заданим у ньому бінарним відношенням , G = <M, R> , де М – носій графа (множина вершин); R – сигнатура графа (множина дуг).

Приклад.Побудувати граф G=<M,R>, що задає відношення R з попереднього прикладу.

□ Шуканий граф показаний на мал. 1.9 : Рис. 1.9

Тут вершинами графа (кружки або точки) є елементи множини М={a,b,c,d,e}, тобто пристрою ЕОМ. Дуги (стрілки) указують напрямок потоку інформації. При цьому, як , то вершина - початок дуги, а вершина - кінець дуги. ■

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Приклад.Розглянемо відповідність, зображена на мал. 1.7	\|	Фактор – множина

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.