Связь бинарных отношений и графов.

υ = {x₁, x₂, x₃, x₄}

Если рассматривать некоторое отношение R, то мы прежде всего рассмотрим 2 элемента.

Рассмотрим возможно ли описанное отношение R перенести на графы

Бинарные отношения	графы
MxM образует всевозможные пары из множества М. 1) Простейшие подмножество R= 2) R=M^2 полному бинарному отношению соответсвует неориентированый граф с петлями в вершинах, такой граф называют полным. 3)	1) - нуль граф т.е. в каждой вершине петля в неориентированом графе или ребро, когда xi = xj 2) xi U xj Среди множества графов соответствующих отношению R, есть смысл рассмотреть класс изоморфных графов. df два графа изоморфны Y=Y` если содержат одинаковое кол-во вершин с одинаковым расположением ребер между вершинами.

X1

Х1

Изоморфные графы

рассмотрим R –отношение эквивалентности.

Ему свойственны 3 признака:

1. рефлексивность aRa

2. симметричность aRb → bRa

3. транзитивность aRb, bRc → aRc

когда мы рассматриваем это отношение на множестве М, то мы видели что оно делит все множество на классы.

Взяв множество вершин графа и выделив а так же собрав через эквивалентности все элементы R(x_i) разобьем R(x_i) на не пересекающиеся подмножества , то , где i, j = 1,…n

Но внутри класса выбранные вершины связаны ребрами => отношение эквивалентности переносимое на графы разбивает множества вершин непересекаемые подмножества. Внутри этих классов существует связь вершин и ребер. Между классами связь отсутсвует.

Df1. Два графа G₁ и G₂ называются изоморфными, если существуют взаимно однозначное отображение между множествами их вершин обладающие тем свойством, что число ребер соденят любые две вершины в графе G₁ = числу ребер, соедененных соответсвенно вершины в графе G₂.

Граф который не содержит кратных ребер и петель называется простым

ρ(υ ₁,υ₂) = 3 – кратность

L(υ₃,υ₂) – петля

Общий граф содержит графы, как простые так и сложные.

Два орграфа G₁ и G₂ называются изоморфными, если существует изофорфизм между их основаниями (не ориентированный граф) и направленными.

1. a R a => на графе имеется петля

2. a R b " b R a, то на графе

3. a R b, b R c " a R c, то

Можно сказать, что в целом граф удовлетворяющей отношению эквивалентности есть объединение подграфов

Частичное упорядочивание – особое отношение, которое удовлетворяет следующим свойствам

1. а≥а

2. а≥b b≥a " b = a

3. a≥b b≥c " a≥c

При задании такого отношения на графах мы видим следующую картину: этому соотношению будет соответствовать неориентированный граф с петлями в вершинах и с транзитным замыканием ребер.

Если рассматривать строгое упорядочивание, то оно будет выглядеть следующим образом:

1. a не больше a

2. a > b, b > c " a > c

На графе, соответственно этому отношению, не будет петель, будет просто транзитивное замыкание

Все остальные случаи будут являться комбинацией этих простых

Если взять бином отношение R, то над множеством можно производить операции.

Df1. Если взять исходный граф Y и поставить его на множестве вершин графов, то полному отношению соответствующих графов U(i) заданному соответственно графом Y(R) => граф от

Y(R)=U(E)-Y(R)

Df2. Если взять отношение aR₁b и aR₂b, то их объедением будет а(R`₁ U R₂) в, т.к. и , то мы можем взять либо а R₁ b либо a R₂ b или при R₁ = R₂

a R₁ b или a R₂ b.

Если взять 2 графа Y(R₁) и Y(R₂), то

Сумма бинарных отношений соответствует операция вида:

Если рассматривать операцию пересечения, тогда когда . Если отношения полностью совпадают то R₁=R₂=R₃.

a = b

для каждого отношения R₁ и R₂ строится свой граф. Пересечение отношений есть новый граф, который является общей частью двух графов

Сами биномиальные отношения можно интерпретировать на графы. И весь рассмотренный аппарат отношений можно перенести на графы => между графами и биномиальными отношениями существует тесная связь.

Дата добавления: 2015-09-01