Тема 13.3. Отношения порядка и эквивалентности на графе

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

Рефлексивность: Условие – истинно. Это означает эквивалентность вершины самой себе. Однако, при желании, это условие можно рассматривать как наличие петли в вершине .

Транзитивность: Условие «если и , то » означает, что вершины последовательно встречаются на одном и том же пути.

Антисимметричность: «если и , то ». Левая часть этого выражения говорит о том, что существует путь из в и путь из в . Т.о. в графе существует контур, на котором лежат вершины и . Из правой части свойства вытекает, что вершины лежащие на одном контуре – эквивалентны. Будем рассматривать этот вывод, как определение отношения эквивалентности на графе и покажем, что такое определение удовлетворяет всем условиям отношения эквивалентности.

Рефлексивность: Условие – вытекает из определения отношения эквивалентности. Всегда можно считать, что существует путь из в длины 0.

Транзитивность: Условие «если и , то » так же очевидно, так как если в графе есть контур, содержащий вершины и , и есть контур, содержащий и , то существует контур, содержащий вершины и .

Симметричность: Условие «если , то Þ » так же очевидно и вытекает из определения отношения эквивалентности и понятия контура графа.

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

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

Дата добавления: 2015-10-28