заказ №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 расположены на двух последних уровнях).