На этом шаге мы определим различные виды отношений.
- Определение.
- Под бинарным отношением на множестве M мы понимаем произвольное подмножество E множества MxM.
Рассмотрим ориентированный граф, в котором любая дуга (v,w) имеется только в том случае, если элементы v и w, представляемые вершинами v и w, находятся в данном бинарном отношении r, т.е. vrw. Такой граф является исчерпывающей и наглядной формой представления отношения r, так как он полностью перечисляет все упорядоченные пары вершин-элементов, для которых отношение r имеет место.
Графы отношений могут обладать специальными свойствами: рефлексивностью, симметричностью, антисимметричностью, транзитивностью и т.д., отражающими соответствующие свойства отношений.
- Определение 1.
- Отношение r называется рефлексивным на множестве M, если для всякого
a принадлежащего M верно ara. Отношение r называется нерефлексивным на множестве M,
если ни для какого a принадлежащего M не выполняется ara.
Будем говорить, что граф является рефлексивным, если каждая вершина имеет петлю, и антирефлексивным, если ни одна вершина петли не имеет.
- Определение 2.
- Отношение r называется симметричным на множестве M, если для каждой
пары a и b элементов M из arb следует bra. Отношение r называется антисимметричным на множестве
M, если для несовпадающих элементов a и b из arb следует не bra.
Будем говорить, что граф является симметричным, если каждой дуге (v,w) соответствует дуга (w,v), и антисимметричным, если каждая дуга (v,w) исключает существование дуги (w,v) (заметим, что антисимметричный граф может как иметь петли, так и не иметь их!).
- Определение 3.
- Отношение r называется транзитивным на множестве M, если для любых
трех элементов a, b и g, принадлежащих M, из arb и brg следует arg. Отношение r называется
антитранзитивным на множестве M, если для любых трех
элементов a, b и g, принадлежащих M, из arb и brg следует не arg.
Будем говорить, что граф является транзитивным, если существование дуг (v,w) и (w,u) означает существование дуги (v,u), и антитранзитивным, если существование дуг (v,w) и (w,u) означает несуществование указанной дуги.
- Определение 4.
- Отношение r на множестве M, которое одновременно рефлексивно, симметрично и транзитивно, называется отношением эквивалентности.
Графом отношения эквивалентности называется граф, являющийся
- рефлексивным,
- симметричным и
- транзитивным.
- Определение 5.
- Отношение r называется полным отношением, если в нем для всякой пары
a, b несовпадающих элементов множества M имеет место arb, либо bra. Отношение, не являющееся полным, называется неполным.
Граф полного отношения (полный граф) характеризуется наличием хотя бы одной дуги для любой пары вершин. В графе неполного отношения некоторые пары вершин не соединены дугами.
- Определение 6.
- Отношение r называется отношением порядка, если оно
- антисимметричное и
- транзитивное.
Соответственно графом отношения порядка называется антисимметричный и транзитивный граф.
- Определение 7.
- Отношение r называется отношением полного порядка (полным порядком), если оно
- антисимметричное,
- транзитивное и
- полное.
Соответственно графом отношения полного порядка называется антисимметричный, транзитивный и полный граф.
Отношение r называется отношением неполного порядка (неполным порядком), если оно
- антисимметричное,
- транзитивное и
- неполное.
Соответственно графом отношения неполного порядка называется антисимметричный, транзитивный и неполный граф.
- Определение 8.
- Отношение называется отношением строгого порядка, если оно
- антирефлексивно,
- антисимметрично и
- транзитивно.
Соответственно графом отношения строгого порядка называется антирефлексивный, антисимметричный и транзитивный граф.
Отношение называется отношением нестрогого порядка, если оно
- рефлексивно,
- антисимметрично и
- транзитивно.
Соответственно графом отношения нестрогого порядка называется рефлексивный, антисимметричный и транзитивный граф.
Конечно, отношение строгого порядка может быть как полным, так и неполным, и отношение нестрогого порядка тоже может быть как полным, так и неполным.
Определения разных видов порядка сведем в таблицу [1, с.87]:
| Порядки | Отношения | |||||
|---|---|---|---|---|---|---|
| Антисимметричное | Транзитивное | Рефлексивное | Антирефлексивное | Полное | Неполное | |
| Строгий | + | + | + | |||
| Нестрогий | + | + | + | |||
| Полный | + | + | + | |||
| Неполный | + | + | + | |||
(1) Березина Л.Ю. Графы и их применение. - М.: Просвещение, 1979. - 143 с.
На следующем шаге мы познакомимся с топологической сортировкой.
