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

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

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

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

Свойства соответствий:
1. Соответствие называется функциональным, если его график функционален.
2. Соответствие называется инъективным, если его график инъективен.
3. Соответствие называется всюдуопределенным, если проекция графика на первую ось совпадает с областью отправления. пр.G₁ = X.
4. Соответствие называется сюръективным, если проекция графика на вторую ось совпадает с областью прибытия пр.G₂ = Y
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 -местная функция типа φ: М × М ×... × М ® М (иное обозначение φ: Мⁿ ® М) называется п -арной операцией на множестве М. В таких случаях говорят, что множество М замкнуто относительно операции φ (резуль­тат выполнения операции φ на М принадлежит М). В частности:

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].

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

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

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

где B_ij:
1, если вершина V_i ∈ ребру e_j
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 имеет дополнительное отношение (или отрицание) , которое выполняется тогда и только тогда, когда не выполняется R. Граф G () является дополнительным графом для G (R) по отношению к полному графу U, определенному на множестве вершин V.

G () = U (V) - G (R),
или U (V) = G (R) È G ().

Для любого отношения 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, С), то всегда есть и ребро (А, С), их замыкающее.