13. Декартово произведение множеств

Определение. Декартовым (прямым) произведением множеств А и В (обозначение AxB) называется множество всех упорядоченных пар (a;b), таких, что aEA, bEB. В частности, если А=В, то обе координаты принадлежат множеству А, такое произведение обозначается А². Аналогично, прямым произведением множеств A₁, A₂, ... A_n называется множество всех векторов (a₁, a₂, ... a_n) длины п, таких, что a₁EA₁,a₂EA₂ ... a_nEA_n.

например даны множества A={1,2,3} и B={a,b} их декартово произведение A×B={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}

14. Соответствия (область отправления, область прибытия, область определения, область значений, образ, прообраз). Примеры.

15. Виды соответствий (инъективное, сюръективное, всюдуопределенное, функциональное соответствие).

Понятие соответствия

Пусть заданы два множества X и Y. Если для каждого элемента x∈X

указан элемент y∈Y, с которым сопоставляется x, то говорят, что между

множествами X и Y установлено соответствие. Иначе говоря, соответствием

называется тройка множеств Г=(X,Y,G), где G⊂X×Y. Множество X

называется областью отправления, Y – областью прибытия, G – графиком

соответствия. Если (x,y)∈G, то множество первых проекций (Пр1G)

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

(Пр2G) – областью значений этого соответствия, G – графиком

соответствия.

Два соответствия равны, тогда и только тогда, когда равны их области

отправления, области прибытия и графики.

В соответствии (X,Y,G) множество всех y∈Y, которые сопоставляются

элементу x∈X, называется образом x в Y.

Множество же всех x∈X, которым сопоставляют элемент y∈Y, называется

прообразом y в X.

Соответствие называется всюду определенным, если множество Пр1G=X,

то есть его область определения совпадает с областью отправления (в

противном случае говорят о частичном соответствии). Если же Пр2G=Y, то

соответствие называют сюръективным, или накрывающим. Это означает, что

область значений соответствия совпадает с его областью прибытия.

Соответствие (X,Y,G) называется функциональным (или однозначным),

если образом любого элемента из Пр1G является единственный элемент из

Пр2G. График такого соответствия называется функциональным. Это

означает, что в нем нет пар с одинаковыми первыми и различными вторыми

компонентами. Соответствие называется инъективным, если любому

элементу из Пр2G соответствует единственный элемент из Пр1G

Соответствие между X и Y называется взаимно-однозначным (или

биективным), если оно всюду определено, сюръективно, функционально и

инъективно.

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

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

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

Определение: Граф, содержащий только ребра, называется ориентированным.

Определение: Граф, содержащий только дуги, называется неориентированным.

Определение: Пара вершин может соединяться двумя или более ребрами одного направления, такие ребра называются кратными.

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

Определение: Вершины, соединенные ребром или дугой называются смежными,

Определение: Дуги, имеющие общие вершины называются смежными.

Определение: Ребро и любая из двух ее вершин называется инцидентными.