заказ №42945
1. Докажите тождества, используя диаграммы Венна.
2. Дано: A=Ja,b,c}, В={ 1,2,3,4}, Р,сАхВ, Р:сВ\ Найдите область
определения и область значений отношений Р|, Р;. Изобразите Р(, Р; графически. Найдите Р;1. Проверьте графически и с помощью матрицы [Р;]- является ли отношение Р; рефлексивным, симметричным, антисимметричным, транзитивным? Являются ли отношения Р],Р; функциями? Постройте три функции (если это возможно) f:A—»В, чтобы одна из них была сюрьективной, другая инъективной, а третья биективной.
3. Даны графы G, и G;. Являются ли графы G| и G; изоморфными. Постройте диаграмму графа изоморфного G|. Найдите G]<~iG;, GiuGi, G|®G; и изобразите результат графически. Для графа GinG; найдите матрицу смежности, матрицу инцидентности, списки смежности, компоненты сильной связности, маршрут (но не цепь) длины 5, (простую) цепь, (простой) цикл, исходящие из вершины 1.
4. Найдите степени всех вершин, радиус и диаметр графа G. Произведите поиск графа G в ширину и в глубину.
5. Найдите матрицы фундаментальных циклов, фундаментальных разрезов графа G. Проведите раскраску графа G по методу последовательной раскраски. Является ли изображенный граф G планарным?
6. Для упорядоченного дерева G выпишите его представление в форме (г,Т|,...,ТО- постройте структуру областей и уступчатый список для графа G. Постройте бинарное дерево, соответствующее G.
7. Взяв за основу бинарное дерево, построенное в задания 6, постройте дерево сортировки, взяв в качестве ключа вершины номер ее обхода по внутреннему порядку.
8. А) Постройте дерево сортировки по заданной последовательности ключей (считайте, что данные ключи одновременно являются и обозначением узла);
Б) База данных содержит N записей (узлов). Сколько максимум узлов надо обойти, чтобы найти нужную запись, если: а) база данных организованна как упорядоченный массив; б) база данных организованна как выровненное дерево (т.е. узлы, степень которых меньше 2 расположены на двух последних уровнях).