![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Связь бинарных отношений и графов.
υ = {x1, x2, x3, x4}
Рассмотрим возможно ли описанное отношение R перенести на графы
![]() ![]() ![]()
рассмотрим R –отношение эквивалентности. Ему свойственны 3 признака: 1. рефлексивность aRa 2. симметричность aRb → bRa 3. транзитивность aRb, bRc → aRc
Но внутри класса выбранные вершины связаны ребрами => отношение эквивалентности переносимое на графы разбивает множества вершин непересекаемые подмножества. Внутри этих классов существует связь вершин и ребер. Между классами связь отсутсвует. Df1. Два графа G1 и G2 называются изоморфными, если существуют взаимно однозначное отображение между множествами их вершин обладающие тем свойством, что число ребер соденят любые две вершины в графе G1 = числу ребер, соедененных соответсвенно вершины в графе G2.
Граф который не содержит кратных ребер и петель называется простым ρ (υ 1, υ 2) = 3 – кратность L(υ 3, υ 2) – петля Общий граф содержит графы, как простые так и сложные.
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. 2. a > b, b > c " a > c На графе, соответственно этому отношению, не будет петель, будет просто транзитивное замыкание Все остальные случаи будут являться комбинацией этих простых Если взять бином отношение R, то над множеством Df1. Если взять исходный граф Y и поставить его на множестве вершин графов, то полному отношению соответствующих графов U(i) заданному соответственно графом Y(R) => граф от Y(R)=U(E)-Y(R) Df2. Если взять отношение aR1b и aR2b, то их объедением будет а(R`1 U R2) в, т.к. a R1 b или a R2 b. Если взять 2 графа Y(R1) и Y(R2), то Сумма бинарных отношений соответствует операция вида: Если рассматривать операцию пересечения, тогда
для каждого отношения R1 и R2 строится свой граф. Пересечение отношений есть новый граф, который является общей частью двух графов Сами биномиальные отношения можно интерпретировать на графы. И весь рассмотренный аппарат отношений можно перенести на графы => между графами и биномиальными отношениями существует тесная связь.
|