Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

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

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

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

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

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

а

Рис. 188а

Рис. 1886

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

ОТ Х2 К X].

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

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы