Главная > Методы обработки данных > Графы, сети и алгоритмы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

5.2. Графы и отношения

Бинарное отношение на множестве представляет собой набор упорядоченных пар из элементов множества X. Например, если X — множество людей, a R — отношение «является сыном», то упорядоченная пара означает, что является сыном . Этот факт обозначается также

Наиболее удачный способ представления бинарного отношения R на множестве X — с помощью ориентированного графа, вершины которого представляют собой элементы множества X, а дуги — упорядоченные пары элементов, определяющие отношение

Рис. 5.7. Ориентированный граф, представляющий отношение «является делителем».

Например, на рис. 5.7 приведено представление отношения «является делителем» на множестве

Рассмотрим множество и отношение R на множестве X:

1) R называется рефлексивным, если любой элемент входит в отношение R с самим собой, т. е. для любого

2) R называется симметричным, если влечет за собой

3) R называется транзитивным, если влечет за собой

4) R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Если R — отношение эквивалентности на множестве S, то последнее однозначно разбивается на такие подмножества что элементы у множества S принадлежат тогда, когда Подмножества называют классами эквивалентности, порожденными отношением R на множестве

Пусть множество X состоит из положительных целых чисел. Тогда

1) отношение «является делителем» рефлексивно и транзитивно;

2) отношение «равно» рефлексивно, симметрично и транзитивно, следовательно, является отношением эквивалентности. Ориентированный граф, представляющий рефлексивное отношение, называется рефлексивным ориентированным графом. Подобным образом определяются симметричные и транзитивные ориентированные графы. Относительно этих графов можно сделать следующие замечания:

1. В рефлексивном ориентированном графе при каждой вершине имеется инцидентная ей петля.

2. В симметричном ориентированном графе между любыми смежными вершинами имеются две противоположно ориентированные дуги. Поэтому, если ребро поставить в соответствие паре противоположно ориентированных дуг, можно рассматривать неориентированный граф как представление симметричного отношения.

3. Дуга присутствует в транзитивном графе G, если из вершины имеется ориентированный путь в вершину

<< Предыдущий параграф Следующий параграф >>
Оглавление