Задание 1 - вариант №4
Докажите тождества, используя диаграммы Венна.
Задание 2 - вариант №8
Дано: А={а,b,с}, В={1,2,3,4}, P1АВ, P2В2. Найдите область определения и область значений отношений P1, Р2. Изобразите P1, Р2 графически. Найдите . Проверьте графически и с помощью матрицы [Р2], является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным? Являются ли отношения P1,P2 функциями? Постройте три функции (если это возможно) f:AB, чтобы одна из них была сюръективной, другая инъективной, а третья биективной.
Задание 3 - вариант №4
Даны графы G1 и G2. Являются ли графы G1 и G2 изоморфными. Постройте диаграмму графа изоморфного G1. Найдите G1G2, G1G2, G1G2 и изобразите результат графически. Для графа G1G2 найдите матрицу смежности, матрицу инцидентности, списки смежности, компоненты сильной связности, маршрут (но не цепь) длины 5, (простую) цепь, (простой) цикл, исходящие из вершины 1.
Задание 4 - вариант №8
Найдите степени всех вершин, радиус и диаметр графа G. Произведите поиск графа G в ширину и в глубину.
Задание 5 - вариант №1
Найдите матрицы фундаментальных циклов, фундаментальных разрезов графа G. Проведите раскраску графа G по методу последовательной раскраски. Является ли изображенный граф G планарным?
Задание 6 - вариант №2
Для упорядоченного дерева G выпишите его представление в форме (r,T1,…,Tk), постройте структуру областей и уступчатый список для графа G. Постройте бинарное дерево, соответствующее G.
Задание 7 - вариант №1
Взяв за основу бинарное дерево, построенное в задания 6, постройте дерево сортировки, взяв в качестве ключа вершины номер ее обхода по внутреннему порядку.
Задание 8 - вариант №4
А) Постройте дерево сортировки по заданной последовательности ключей (считайте, что данные ключи одновременно являются и обозначением узла);
Б) База данных содержит N записей (узлов). Сколько максимум узлов надо обойти, чтобы найти нужную запись, если: a) база данных организованна как упорядоченный массив; б) база данных организованна как выровненное дерево (т.е. узлы, степень которых меньше 2 расположены на двух последних уровнях).
|