21. Алгебраические свойства операций.
Свойства операций над множествами:
22. Мощность множеств. Взаимно-однозначное соответствие. Равномощность.
Мощность множества — это обобщение понятия количества элементов множества, которое имеет смысл для всех множеств, включая бесконечные.
Взаимно однозначное соответствие - такое соответствие между элементами двух множеств, при котором каждому элементу первого множества соответствует один определенный элемент второго множества, а каждому элементу второго множества - один определенный элемент первого множества.
Множества A и B называются равномощными , если существует взаимно однозначное отображение этих множеств. Понимать это можно так: множества равномощны, если в них одинаковое количество элементов.
23. Операции над графами.
Пусть даны 2 графа G1(V1,E1) и G2(V2,E2). Ака и над множествами можно выполнить следующие операции:
1. Объединение.
G1UG2 => G3(V1UV2, E1UE2) //т.е. граф, мн-во вершин и ребер которого является объединением соответствующих множеств G1 и G2.
2.Произведение.
Произведением графов G1 и G2 называется граф G3 (V1∩V2, E1∩E2).
3.Дополнение.
Дополнением G(V,E) называется граф Ḡ(V,Ē), т.е. граф, у которого множество вершин тоже, а ребро входит в Ē, если оно не входит в E.
4.Симметричная разность.
G1∆G2 называется реберно-порожденный граф G3(E3,V3), где E3 = E1∆E2 или E3 = (E1UE2)\( E1∩E2), т.е. Е3 – это объединение Е1 и Е2, из которого удалены общие ребра для Е1 и Е2, а V3 – это объединение V1 и V2, из которого удалены совпадающие вершины, которые не инцидентны ребрам E3.
5.Удаление вершины.
Удалением вершины Vi из графа G(V,E) называется операция, которая удаляет из графа G вершину Vi и все инцидентные ей ребра.
6.Удаление ребра.
Удалением ребра ei из графа G(V,E) называется операция, которая из графа G порождает граф G(V,E\e). Концы ребра ei не удаляются.
24. Прямое произведение множеств А и В, множество Аn.
/* Внимание, в информации ниже заменяем Х на А, а Y на В */
Произведение двух множеств
Пусть даны два множества X и Y. Прямое произведение множества X и множества Y - есть такое множество , элементами которого являются упорядоченные пары (x,y)для всевозможных и .
Отображения произведения множеств в его множители ( и ) называют координатными функциями.
Аналогично строятся произведения нескольких множеств.
Комментарии
Строго говоря, тождество ассоциативности не имеет места, но в силу существования естественного взаимно однозначного соответствия между множествами и этим различием можно зачастую пренебречь.
Декартова степень
n-я Декартова степень множества X определяется для целых неотрицательных n, как n-кратное Декартово произведение X на себя:
При положительных n Декартова степень Xn состоит из всех упорядоченных наборов (кортежей) элементов из X длины n.
При n = 0, Декартова степень X0 по определению содержит единственный элемент — пустой кортеж.
Прямое произведение семейства множеств
Дальнейшее обобщение понятия прямого произведения приводит к произведениям по индексному множеству I (возможно, бесконечному): X = ΠXi, элементы которого сопоставляют каждому индексу i из I элемент множества Xi.