Поделиться Поделиться

Унарные и бинарные операции. Свойства бинарных операций)

Соответствия и их свойства. Основные определения)

Соответствиемежду множествами Аи В называется подмножество G прямого произведения этих множеств:G подмножествоА ×В. Если (a, b)принадлежит G, то говорят, что bсоответствует апри соответствии G.

Множества Аи Вназываются равномощными , если между их элементами можно установить взаимно-однозначное соответствие.

Свойства соответствий:
1.Соответствие называется функциональным , если его график функционален.
2.Соответствие называется инъективным , если его график инъективен.
3.Соответствие называется всюдуопределенным , если проекция графика на первую ось совпадает с областью отправления. пр.G1 = X.
4.Соответствие называется сюръективным , если проекция графика на вторую ось совпадает с областью прибытия пр.G2 = Y
5.Соответствие называется биективным(взаимно-однозначным), если оно функционально, инъективно, всюдуопределено и сюръективно.

Функциональное соответствие. Функции и отображения)

Функциональным соответствием Унарные и бинарные операции. Свойства бинарных операций) - Инвестирование - 1 на множестве Унарные и бинарные операции. Свойства бинарных операций) - Инвестирование - 2 называют бинарное отношение Унарные и бинарные операции. Свойства бинарных операций) - Инвестирование - 3 , в котором каждый элемент множества Унарные и бинарные операции. Свойства бинарных операций) - Инвестирование - 4 имеет единственный образ во множестве Унарные и бинарные операции. Свойства бинарных операций) - Инвестирование - 5 .

Функциейназывается любое функциональное соответствие между двумя множествами. Если функцияfустанавливает соответствие между множествами Аи В , то говорят, что функция имеет вид A ® B(обозначение f: A ® B ). Каждому элементу aиз своей области определения функция f ставит в соответствие единственный элемент bиз области значений. Это записывается в традиционной форме f(a)=b . Элемент aназывается аргументом функции, элемент b– её значением.

Отображением А в В называется всюду определённая функция f: A ® B.Отображением А на В называется всюду определённое и при этом сюръективное функциональное соответствие f: A ® B.

Отображение типа A ®Aназывается преобразованиеммножества A .

Унарные и бинарные операции. Свойства бинарных операций)

Операцией называют функцию, все аргументы и значе­ния которой принадлежат одному и тому же множеству. В общем случае n -местная функция типа φ: М × М × ... × М ® М(иное обозначение φ: Мn ® М ) называется п -арной операцией на множестве М . В таких случаях говорят, что множество Мзамкнуто относительно операции φ(резуль­тат выполнения операции φна Мпринадлежит М ). В частности:

1. Функция одного аргумента φ (х) = у , имеющая тип φ: М ® М , называется унарной операцией.

Примеры унар­ных операций:

• элементарные функции еx, log x, sin x и др.

• операция над множествами - дополнение Ā ;

• отображения типа А ® А , такие как преобразования, перестановки;

2. Функция двух аргументов φ (х, у) = z , имеющая тип φ: М × М® М , называется бинарной операцией.

Примеры бинарных операций:

• арифметические операции: сложение, вычитание, умно­жение, деление, возведение в степень;

• операции над множествами: пересечение ᴖ, объедине­ние ᴗ и, разность \ ;

• операция композиции функций, отображений, отноше­ний и др. Если над элементами a,bМвыполняется опера­ция φ , дающая результат zМ , то это записывается часто как а φ b = z .

Свойства бинарных операций:

1) φ- ассоциативна, если для любых а,b,сиз М

(а φ b) φ с = а φ (b φ с)

(арифметические операции сложения и умножения, опера­ции пересечения и объединения множеств, композиция ото­бражений - ассоциативные операции).

Выполнение этого условия (свойства ассоциативности) означает, что скобки в выражении a φ b φ сможно не расставлять;

2) φ- коммутативна, если для любых а, b, с

a φ b = b φ a

(арифметические операции сложения и умножения, опера­ции пересечения и объединения множеств - коммутативные операции; арифметические операции вычитания и деления, операция разности множеств, композиция перестановок и преобразований типа А ® Аконечного множества - некоммутативны);

3) φ- дистрибутивна слева относительно операции ψ , если для любых а, b, с

а φ (b ψ с) = (а φ b) ψ (а φ с)

и φдистрибутивна справа относительно операции ф, если для любых а, b, с

(а ψ b) φ с = (а φ с) ψ (b φ с)

(арифметические операции умножения и деления дистри­бутивны относительно операций сложения и вычитания сле­ва и справа, но не наоборот: операции сложения и вычита­ния недистрибутивны относительно операции умножения и деления; операции объединения и пересечения множеств ди­стрибутивны относительно друг друга слева и справа).

Теория графов. Основные понятия)

Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами).

Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, также называются смежными (или соседними).

Граф называется ориентированным (или орграфом) ,если некоторые ребра имеют направление. Этоозначает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой).

Помимо этого, в теории графов рассматриваются также мультиграфы – это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами.

Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней.

Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).

Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.

Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем).

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

Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов).

Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.

Лемма 1 . Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур.

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

Способы задания графов)

Граф G=(V,E) можно задать списком вершин и ребер. Можно задать и геометрически, нарисовав его на плоскости или любой другой поверхности и отождествив его вершины с точками на плоскости, а ребра с отрезками, соединяющими смежные (соседние) вершины.

Определение : Матрица смежности (соседства) вершин(p, q)– графа G=(V,E)с p вершинами есть квадратная симметричная матрица [p x p] .

Унарные и бинарные операции. Свойства бинарных операций) - Инвестирование - 6

где aij :
- 1, если вершины Vi , Vj– соседние
- 0, в противном случае

Замечание : Всякому графу соответствует его бинарная симметричная матрица смежности. Всякая бинарная симметричная квадратная матрица с нулевой диагональю соответствует некоторому графу.

Определение : Матрица инциденций (соответствий) (p, q) – графа G=(V,E)с p вершинами и q ребрами есть[p x q] матрица

Унарные и бинарные операции. Свойства бинарных операций) - Инвестирование - 7

где Bij :
1, если вершина Vi ребру ej
0, в противном случае

Замечание : для всякого графа можно построить соответствующую ему бинарную матрицу инциденций.

12. ( Операции над частями графов. Графы и бинарные отношения)

Операции над графами:

1)удаление вершины vиз графа Gприводит к подграфу G-vграфа Gбез вершины v и принадлежащих вершине v ребер.
2)Удаление ребра eиз графа G=(V,E)при сохранении вершин приводит к подграфу G-e=(V,E – {e})
3)Добавление ребра e = (u, v)к графу G=(V,E) , содержащему вершины u,v, приводит к графу G+e=(V,E∪{e})

Бинарное отношение Rопределяется как соотношение A R B , которое выполняется для некоторых пар элементов заданного множества V . В соответствии с этим бинарное отношение может быть представлено в виде графа с множеством вершин V , у которого ориентированное ребро (А, B)присутствует тогда и только тогда, когда выполняется отношение A R B .

Обратно, любой граф определяет бинарное отношение Rна множестве своих вершин V , если наличию ребра (А, B)соответствует выполнение A R B .

Имеется, однако, небольшое различие между этими двумя понятиями. Приписывать отношению кратность обычно нет надобности. Поэтому говорить о взаимно-однозначном соответствии между бинарное отношение и графом можно лишь для графа с однократными ребрами.

Нуль-граф отвечает нулевому отношению А Æ B , которое не выполняется ни для одной пары элементов.

Полный граф Uотвечает универсальному отношению А U B , которое выполняется для любой пары элементов.

Каждое отношение Rимеет дополнительное отношение (или отрицание) Унарные и бинарные операции. Свойства бинарных операций) - Инвестирование - 8 , которое выполняется тогда и только тогда, когда не выполняется R . ГрафG( Унарные и бинарные операции. Свойства бинарных операций) - Инвестирование - 8 )является дополнительным графом для G(R)по отношению к полному графу U , определенному на множестве вершин V .

G( Унарные и бинарные операции. Свойства бинарных операций) - Инвестирование - 8 ) = U(V) - G(R) ,
или U(V) = G(R) È G( Унарные и бинарные операции. Свойства бинарных операций) - Инвестирование - 8 ) .

Для любого отношения Rсуществует обратное отношение R* :

Соотношение B R* а выполняется тогда и только тогда, когда выполняется А R B.

Очевидно, что граф G(R*) есть обратный граф для G(R), то есть G(R) и G(R*) – это ориентированные графы с вершинами V и противоположной ориентацией ребер.

Если R* = R (т. е. A R B = A R* B), то такое отношение называется симметричным. В этом случае вершины А и B должны быть соединены ориентированными ребрами (двумя) по одному в каждом направлении. Это соответствует одному неориентированному ребру. Таким образом, симметричным отношениям соответствуют неориентированные графы.

Кроме симметрии у отношений есть свойство рефлексивности: А R а Выполняется для любых А Î V . Соответствующий граф имеет петлю в каждой вершине.

Если А R а не выполняется ни для какой А Î V , то отношение антирефлексивно, и ему соответствует граф без петель.

Если из A R B и B R с следует А R с, то отношение транзитивно. Ему соответствует граф G(R), в котором если есть ребра (A, B) и (B, С), то всегда есть и ребро (А, С), их замыкающее.

← Предыдущая страница | Следующая страница →