Вариант 7.
Докажите тождества, используя диаграммы Виенна.
A\\(BC)=(A\\B)(A\\C)
Задание 2.
Вариант 10.
A={a, b, c}, B={1, 2, 3, 4}. PAB, PB.
1. Найдите область определения и область значений отношений P и P.
2. Изобразите P и P графически.
3. Найдите P.
4. Проверьте графически и с помощью матрицы [P], является ли отношение P рефлексивным, симметричным, антисимметричным, транзитивным?
5. Являются ли отношения P и P функциями?
6. Постройте 3 функции (если это возможно) f:AB, чтобы одна из них была сюръективной, другая коньюктивной, а третья биективной.
P ={(a, 3), (a, 2), (b, 2), (b, 3), (c, 1), (c, 4) };
P ={(1, 1), (1, 2), (2,2), (3, 3), (4, 1), (4, 4)}.
Задание 3.
Вариант 6.
Даны графы G и G.
1. Являются ли графы G и G изоморфными ?
2. постройте диаграмму графа, изоморфного G.
3.1.Найдите G G.
3.2.Найдите G G.
3.3.Найдите G G и изобразите результаты графически.
Для графа G G найдите:
4.1. Матрицу смежности.
4.2.Матрицу инциндентности.
4.3.Списки смежности.
4.4.Компоненты сильной связности.
5.1.маршрут( но не цепь) длины 5.
5.2.( простую) цепь.
5.3.( простой ) цикл, исходящий из вершины 1.
Задача 4.
Вариант 1.
Найдите степени всех вершин, радиус и диаметр графа G. Произведите поиск графа в ширину и глубину.
Задание 5.
Вариант 1.
Найдите матрицы фундаментальных циклов, фундаментальных разрезов графа. Проведите раскраску графа по методу последовательной раскраски. Является ли изображенный граф планарным?
Задание 6.
Вариант 6.
Для упорядоченного дерева G выпишите его представление в форме
(r,T,…,Tk), постройте структуру областей и уступчатый список для графа.
Постройте бинарное дерево, соответствующее G.
Задание 7.
Вариант 6.
Взяв за основу бинарное дерево, построенное в задании 6, постройте дерево сортировки, взяв в качестве ключа вершины номер ее обхода по внутреннему порядку.
Задание 8.
Вариант 1.
А) Постройте дерево сортировки по заданной последовательности ключей ( считайте, что данные ключи одновременно являются и обозначением узла);
Б) База данных содержит N записей ( узлов). Сколько максимум узлов надо обойти, чтобы найти нужную запись, если: а) база данных организована как упорядоченный массив; б) база данных организована как выровненное дерево (т.е. узлы, степень которых меньше двух, расположены на двух последних уровнях).
Последовательность поступления 15 данных:
44,32,43,95,16,10,78,57,98,70,37,36,86,39,61.
N=510 (N=500 000 000) |