- •1.Множество. Способы описания множеств. Примеры. Пустое множество. Универсальное множество. Подмножество. Собственное подмножество. Равенство множеств.
- •2.Операции над множествами: объединение, пересечение, разность, симметрическая разность. Дополнение множества. Примеры.
- •3.Свойства операций над множествами.
- •4. Диаграммы Эйлера – Венна.
- •5. Булеан множества. Примеры. Мощность булеана конечного множества.
- •6. Прямое (декартово) произведение. Примеры. Число элементов в декартовом произведении п множеств.
- •7. Бинарное отношение на множестве. Примеры
- •8.Свойства бинарных отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность. Примеры
- •9.Отношение эквивалентности. Классы эквивалентности. Примеры.
- •10. Отношение порядка: строгого и нестрогого. Примеры. Полное отношение.
- •11. Отображение (функция). Примеры. Постоянная функция. Тождественная функция. Образ и прообраз множества
- •13. Операции над отображениями. Суперпозиция отображений, ее свойства. Примеры. Обратное отображение. Примеры. Критерий обратимости отображения. Свойства операции.
- •16. Изоморфизм графов. Примеры.
- •17. Представление графа. Матрицы смежности и инцидентности ориентированного и неориентированного графов. Примеры. Смысл элемента п-й степени матрицы смежности.
- •18. Полный граф. Пустой граф. Дополнение графа. Двудольный граф. Полный двудольный граф. Планарный граф. Однородный граф. Подграф. Частичный граф. Примеры.
- •19. Маршрут в графе. Цепь. Простая цепь. Циклический маршрут. Цикл. Простой цикл. Путь и контур в орграфе. Примеры.
- •20. Достижимость в неориентированном графе. Матрица достижимости, ее нахождение. Компоненты связности графа, их нахождение.
- •21. Достижимость и взаимная достижимость в ориентированном графе. Матрицы достижимости и сильной связности, их нахождение. Компоненты сильной связёности, их нахождение.
- •22.Нахождение кратчайшего пути между двумя вершинами в невзвешенном ориентированном графе. Волновой алгоритм.
- •23.Взвешенный граф. Нахождение кратчайшего пути между двумя заданными вершинами во взвешенном ориентированном графе. Алгоритм Дейкстры.
- •24.Нахождение кратчайшего пути между всеми парами вершин во взвешенном ориентированном графе. Алгоритм Флойда.
- •25 Центр и медиана взвешенного ориентированного графа. Их нахождение.
- •26. Лес. Дерево. Остовное дерево. Цикломатическое число графа. Нахождение минимального остовного дерева. Алгоритм Прима.
6. Прямое (декартово) произведение. Примеры. Число элементов в декартовом произведении п множеств.
Прямым (декартовым) произведением множеств А и В называется множество всех пар (а, в) таких, что а∈ А и в∉ В.
Обозначение: А х В.
Если А = В, то А х В =А2 и называется декартовым квадратом.
Примеры:
1. R – множество действительных чисел, тогда RхR = R2 – векторы (а, в), где а∈R и в∈R, есть координаты точек плоскости.
Такое координатное представление точек плоскости было предложено Декартом и являлось первым в истории примером прямого произведения множеств.
2. Прямое произведение {1, 2, 3, …, 8} х {a, b, c, d, …, h}- есть множество клеток шахматной доски.
3.Рассмотрим множество А, элементы которого символы (буквы, цифры, знаки препинания, знаки операций…), тогда Аn – это слова длиной n (под словом можно понимать текст).
Определение. Декартовым (прямым) произведением множеств А и В (обозначение AxB) называется множество всех упорядоченных пар (a;b), таких, что a∈A, b∈B. В частности, если А=В, то обе координаты принадлежат множеству А, такое произведение обозначается А2. Аналогично, прямым произведением множеств A1, A2, ... An называется множество всех векторов (a1, a2, ... an) длины п, таких, что a1∈A1, a2∈A2 ... an∈An.
Пример 4. Множество - это множество всех упорядоченных пар действительных чисел, геометрической интерпретацией которого служит декартова координатная плоскость.
Координатное представление точек плоскости было впервые предложено Р. Декартом и исторически является первым примером прямого произведения. Поэтому часто прямое произведение множеств называют декартовым произведением.
7. Бинарное отношение на множестве. Примеры
Бинарным отношением на множестве А назавем некоторое подмножество декартного квадрата G<= A²
A²=A*A={(a,b)|a,b€A}; (a,b)€G
Примеры: A=N; A²={(a,b)|a,b€A}
(1,2); (3,4); (10,2)
a)меньше или равно: 3<=4 (3,4)€G; 10не<=2 (10,2)не принадлежит G
б)меньше: 3<4 (3,4)€G; 1<2 (1,2)€G; 10не<2 (10,2) не принадлежит G
в)равно: 3не=4 (3,4)не принадлежитG и (1,2) и (10,2) тоже
г)быть кратным: (10,5)€G; (10,3)не принадлежит G
8.Свойства бинарных отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность. Примеры
Бинарное отношение G на множестве A называется рефлексивным, если (Ya€A) (a,a)€G
Бинарное отношение G на множестве A называется антирефлексивным, если Ya€A (a,a) не€G.
Бинарное отношение G на множестве A называется симметричным, если из условия (a,b)€G следует включение (b,a)€G.
Бинарное отношение G на множестве A называется антисимметричным, если либо не существует элементов a и b таких, что (a,b)€G и (b,a)€G, либо a=b. (Если пользоваться
смыслом операции импликации из математической логики, то
первое условие можно опустить.)
Бинарное отношение G на множестве A называется
транзитивным, если из условий (a,b)€G и (b,c)€G следует, что(a,c)€G .
9.Отношение эквивалентности. Классы эквивалентности. Примеры.
Рефлексивное, симметричное и транзитивное бинарное отношение G на множестве A называется
отношением эквивалентности. Мы будем использовать стандартное обозначение a~b.
Если на множестве A задано отношение эквивалентности, то A=UiAi, где Ai∩Aj=Ø при i≠j и a~b тогда и только тогда, когда они входят в одно множество al. Эти множества называются классами эквивалентности.
1.a~a, Ya€A; 2. a~b=> b~a Ya,b€A; 3. a~b, b~c=> a~c Ya,b,c€A