Отношения на множествах и графы
Каждый ориентированный граф G(X) определяет некоторое отношение на множестве X своих вершин. Это отношение может быть записано как xi G xj. Оно означает, что в графе есть дуга, идущая от xi к xj.
Отношению со свойством рефлексивности (x R х) должна соответствовать на графе петля в вершине. Если это отношение соблюдается во всех вершинах х Î X, то соответствующий граф G(X) должен иметь петлю в каждой своей вершине.
В случае антирефлексивного отношения на множестве X, соответствующий граф ни в одной из вершин не имеет петли.
Симметрическому отношению на множестве X соответствует граф с неориентированными ребрами и, наоборот, граф с неориентированными ребрами определяет некоторое симметрическое отношение.
В случае антисимметрического отношения на графе невозможно присутствие двух дуг (xi, xj), (xj, xi) на графе, то есть существование неориентированного ребра. Кроме того, на этих графах нет петель, то есть соответствующее антисимметрическое отношение антирефлексивно.
Отношение, обладающее свойством тождественности, соответствует графу с антисимметричным отношением на множестве вершин (ориентированному графу) и добавлением петли в каждой вершине. Этот граф не должен иметь контуров.
Рис. 3.18. Свойство транзитивности на графе
Граф, соответствующий транзитивному отношению (рис. 3.18), обладает следующими свойствами: для любой пары ориентированных ребер (дуг) графа (xi, xj), (xj, xk) имеется замыкающая дуга (xi, xk). Можно сказать, что в графе, который соответствует транзитивному отношению, для каждого пути S(xi, xk) имеется дуга (xi, xk) (рис.3.19).
а) б)
Рис. 3.19. Транзитивный (а) и нетранзитивный (б) графы
Отношение, обладающее свойством полноты, определено на множестве вершин полного ориентированного графа.
Нулевое отношение определено на множестве вершин ноль-графа.
Универсальное отношение определено на множестве вершин полного неориентированного графа с петлями. Дополнительное к R отношение `R определено на множестве вершин дополнительного графа Gd(Х) к G(X).
Графы, соответствующие отношению эквивалентности, представляют собой совокупность компонент связности (для каждого класса эквивалентности своя компонента) несвязного графа. Каждая компонента несвязного графа должна быть полным неориентированным графом с петлями (рис. 3.20).
Рис. 3.20. Граф, соответствующий отношению эквивалентности