Графы бинарных отношений.

В случае конечного множества задания Ω отношения удобно представлять графически. Поставим во взаимно-однозначное соответствие эле­ментам конечного множества Ω различные точки на плоскости: x ₁, x ₂, …,, x _n. Проведем дугу от x_i к x_j тогда и только тогда, ког­да выполнено x_iRx_j для соответствующих элементов Ω (при i = j дуга (x_i,x_j) превращается в пет­лю при вершине x_i). Такой геометрический объект является графом (см. раздел "ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ"). Конкретное расположение вершин (точек) и дуг на плоскости не имеет значения; важно только, что с чем соединено и куда направлена стрелка.

Граф является геометрическим представлением отношения, аналогично тому, как график является геометрическим пред­ставлением функции. Геометрический язык полезен, когда граф достаточно прост (либо у него мало вершин, либо он имеет прос­тую структуру). Наоборот, изучать и описывать сложные графы с большим числом вершин часто удобнее в терминах отношений. В дальнейшем будем говорить о графе отношения R, обозначая его G (R).

Приведём пример. Зададим два бинарных отношения на множестве Ω = { a, b, c, d, e } графами, показанными на рис.1a и b..

a

b

Рис.1

Дата добавления: 2015-10-16