Бінарне відношення R у множині М - це підмножина його квадрата: , де .
Елементи перебувають у відношенні R, якщо , - кортеж.
1. Матриця суміжності – це матриця ,
Приклад.Задано блок-схему ЕОМ, запропоновану фон Нейманом, що складається із множини пристроїв М={a,b,c,d,e}, де a – пристрій введення, b – процесор (арифметичний пристрій), c – пристрій керування, d – запам'ятовувальний пристрій, e – пристрій виводу. Якщо із пристрою mi надходить інформація в пристрій т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}, тобто пристрою ЕОМ. Дуги (стрілки) указують напрямок потоку інформації. При цьому, як , то вершина - початок дуги, а вершина - кінець дуги. ■