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

В теории графов применяется математическое понятие, называемое "отношение". В математике отношение определяет некоторую связь между двумя предметами (объектами). В идеальном мире (существующим в сознании людей) и в реальном (физическом) мире существуют разнообразные отношения между предметами. Поэтому математики и специалисты в области компьютеров используют множество различных бинарных (двуместных) отношений. Бинарные отношения могут иметь имена, например "равенство", "отношение порядка" и т.п. Некоторые из бинарных отношений помимо имен имеют стандартные символьные обозначения. Примерами, таких отношений являются "равенство" (стандартное обозначение =), отношения "больше, (>)" и "меньше, (<)" и ряд других отношений.

В общем случае бинарные отношения обозначаются символом . Словосочетание "в общем случае" следует понимать как "все бинарные отношения". Выражение "в общем случае" будет часто встречаться в нашем Курсе в разных контекстах. Кроме бинарных существуют n-арные отношения, но они, в отличие от бинарных отношений, не имеют общего символьного обозначения. Заметим, что n-арные отношения широко используются в теории реляционных баз данных.

Любое бинарные отношение представляется множеством упорядоченных пар элементов. В математике множество элементов обозначается с помощью двух фигурных скобок { }, а упорядоченная пара с помощью символов < >. Множество {<2,4>,<7,3>,<3,3>}, будучи множеством, состоящим из трех упорядоченных пар, есть бинарное отношение. Пара <2,4> является элементом этого бинарного отношения. Элемент бинарного отношения, т.е. упорядоченную пару в общем случае обозначим . Элементы в упорядоченной паре нельзя менять местами и, наоборот, элементы множества можно менять местами и при этом множество не меняется, т.е. два множества с одинаковыми, но по-разному расположенными элементами равны. Например {1,2}={2,1}.

В качестве примера бинарного отношения рассмотрим все упорядоченные пары элементов, которые можно составить на множестве {1,2}. Для множества {1,2} путем перестановки его элементов можно составить всего лишь две упорядоченные пары <1,2> и <2,1>. Набор из двух упорядоченных пар <1,2>, <2,1> является примером бинарного отношения, установленного на множестве двух элементов {1,2}. Если множество состоит из трех элементов, то самое большое бинарное отношение, которое можно построить на нем, состоит из 6-ти упорядоченных пар. Подмножество этого бинарного отношения может состоять, например, только из 3-х упорядоченных пар. Очевидно, что для множества из n элементов самое большое (полное) бинарное отношение

2 будет состоять из Сn = n(n-1) упорядоченных пар. Эти математические рассуждения пригодятся нам при рассмотрении теории графов.

Поскольку бинарные отношения постоянно встречаются в математике и науке о компьютерах, то, часто, прилагательное "бинарное" опускается и вместо словосочетания "бинарное отношение" говорят просто "отношение".

Рассмотрим теперь бинарные отношения, записываемые не в числовом виде, а с помощью слов. Пусть имеется множество, состоящее из двух словесных элементов {"отец-Иван", "сын Ивана-Николай"}. Установленное на нем полное бинарное отношение состоит из двух упорядоченных пар - <отец-Иван, сын-Николай> и <сын-Николай, отец-Иван>. Поименованные бинарные отношения используются в реляционных базах данных.

Математики рассматривают отношения с двух точек зрения. Иногда, они смотрят на них как на самостоятельные объекты. В других случаях они используют отношения совместно с множествами элементов, на которых эти отношения устанавливаются.