Графы бинарных отношений со свойствами

Пусть А — бинарное отношение, заданное на множестве Х₉ и G_A — ориентированный граф этого отношения. Если бинарное отношение А обладает некоторыми алгебраическими свойствами, то эти свойства отражаются на геометрии графа G_A. Проследим эту связь на некоторых специальных классах отношений.

Бинарное отношение А называется рефлексивным, если условие хАх выполняется для любого элемента хе X. Граф рефлексивного отношения является элементарным орграфом и имеет петлю в каждой вершине. Такие графы, так же как и их бинарные отношения, называются рефлексивными.

Бинарное отношение А и его граф G_A называются антирефлексивными, если условие хАх не выполняется ни для какого элемента хе X. Граф антирефлексивного отношения является элементарным орграфом без петель.

Бинарное отношение А и его граф С_А называются симметрическими, если из условия х/Ах₂ следует условие x₂Axi. В симметрическом орграфе для каждой дуги, не являющейся петлей, можно указать нестрого параллельную ей дугу. Для моделирования симметрических бинарных отношений можно использовать неориентированные графы, заменив в орграфе G_A каждую пару нестрого параллельных дуг одним неориентированным ребром. Так, например, симметрический ориентированный граф, представленный на рис. 188а, можно заменить неориентированным графом, представленным на рисунке 1886.

Рис. 188а

Рис. 1886.

Бинарное отношение А и его граф G_A называются антисимметрическими, если из условия xjAx2 следует, что условие Х2АХ1 не выполняется. В антисимметрическом орграфе не существует нестрого параллельных дуг, и существование дуги от х к Х2 гарантирует отсутствие дуги ОТ Х2 К X].

Бинарное отношение А и его граф G_A называются транзитивными, если из условий х/Ах₂ и х₂Ах₃ всегда следует условие х/Ах₃. В транзитивном графе существование пути от вершины х к вершине х' гарантирует существование дуги из х в х