Изображение бинарных отношений графами

Бинарные отношения.

Определение. Бинарное отношение – это любое множество упоря­доченных пар. Другими словами, бинарное отношение – это подмножество прямого произведения двух множеств.

Пример. - бинарное отношение, которое называется отношением равен­ства на множестве натуральных чисел.

Бинарные отношения часто задают описанием.

Пример. Что такое отношение равенства на множестве ?

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

Определение. Если отношение - подмножество прямого произведе­ния , то - бинарное отношение на множестве .

Определение. Граф – это фигура на плоскости, состоящая из конеч­ного числа точек – вершин графа и линий – рёбер графа, соединяющих не­которые из вершин. Ребро графа – это линия, соединяющая какие-либо две вершины графа.

Пример. 1) Бинарное отношение задано как множество пар:

Изобразим бинарное отношение графом:

e

d

b

c

a

2) Бинарное отношение задано своим графом.

c

m

k

Запишем это бинарное отношение как множество пар:

llllllll

Определение. Разбиением множества называется такое семейство его непустых подмножеств, что каждый элемент множества входит в точ­ности в один из членов семейства.

Другими словами, разбиением мно­жества называется совокупность его подмножеств , которые об­ладают следующими свойствами:

1)

2)

3) ,

т.е. разбиение множества есть свойство его не­пустых подмножеств, объединение которых совпадает с множеством , пересечение любых двух из них не пусто.

Пример. Пусть дано множество . Будут ли следующие се­мейства множеств разбиением.

1) ; ; - являются разбиением

2) ; - являются разбиением

3) ; - не являются разбиением

Задача. (НИРС)

Пусть имеет элементов. Сколько существует разбиений множе­ства .

Дата добавления: 2015-03-31