Год сдачи: 2009 Краткое описание: задачи и решения по дискретной математике Задача 1.
Докажите тождество, используя диаграммы Венна. (A U B)\C = (A\C) U (B\C). Задача 2.
Дано: А={а,b,с}, В={1,2,3,4}, P1 Í А×В, P2 Í В2. Найдите область определения и область значений отношений P1, Р2. Изобразите P1, Р2 графически. Найдите P2-1. Проверьте графически и с помощью матрицы [Р2], является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным? Являются ли отношения P1, P2 функциями? Постройте три функции (если это возможно) f:A→B, чтобы одна из них была сюръективной, другая инъективной, а третья биективной. P1 = {(a,1), (a,2), (a,4), (c,3), (c,2), (c,4)} P2 = {(2,1), (3,1), (3,2), (4,1), (4,3)} Задача 3.
Даны графы G1 и G2. Являются ли графы G1 и G2 изоморфными. Постройте диаграмму графа изоморфного G1. Найдите G1G2, G1G2, G1G2 и изобразите результат графически. Для графа G1 найдите матрицу смежности, матрицу инцидентности, списки смежности, компоненты сильной связности, маршрут (но не цепь) длины 5, (простую) цепь, (простой) цикл. Задача 4.
Найдите степени всех вершин, радиус и диаметр графа G. Произведите поиск графа G в ширину и в глубину. Задача 5.
Найдите матрицы фундаментальных циклов, фундаментальных разрезов графа G. Проведите раскраску графа G по методу последовательной раскраски. Является ли изображенный граф G планарным? Задача 6.
Для упорядоченного дерева G выпишите его представление в форме (r,T1,…,Tk), постройте структуру областей и уступчатый список для графа G. Постройте бинарное дерево, соответствующее G. Задача 7.
Взяв за основу бинарное дерево, построенное в задания 6, постройте дерево сортировки, взяв в качестве ключа вершины номер ее обхода по внутреннему порядку.
Решение. Строим дерево поиска (дерево сортировки), совершив обход по внутреннему порядку: ключ вершины номер ее обхода по внутреннему порядку написан над вершиной. Задача 8.
а) Постройте дерево сортировки (поиска) по заданной последовательности ключей (считайте, что данные ключи одновременно являются и обозначением узла);
46 40 82 77 98 75 26 15 23 28 50 74 73 90 79 б) База данных содержит N записей (узлов). Сколько максимум узлов надо обойти, чтобы найти нужную запись, если: 1) база данных организованна как неупорядоченный массив; 2) база данных организованна как выровненное дерево (т.е. узлы, степень которых меньше 2 расположены на двух последних уровнях): N = 95⋅105 (N=95 00 000). |