Дискретная математика 07 |
Контрольная работа 2) В таблице приведены запросы и количество найденных по ним страниц в Интернете.
Какое число страниц (тыс.) будет найдено по запросу: (Шереметьево и Домодедово) или (Домодедово и Внуково) (Шереметьево и Домодедово) или (Домодедово и Внуково) = = Ответ: по данному запросу будет найдено 1100 тыс. страниц. II. Теория графов1) Задан неориентированный граф без петель из пяти вершин строками матрицы смежности в виде шестнадцатеричного числа, первая цифра – первая строка, вторая – вторая строка и т. д. Изобразите соответствующий граф и определите степени всех вершин. Постройте матрицу инциденций. Вариант задания – последняя цифра в номере зачетной книжки. Вариант – 5. Данное шестнадцатеричное число –D43116 Переведем каждую цифру шестнадцатеричного числа в двоичную систему счисления: D16 = 11012 – 1 строка, 416 = 01002 – 2 строка, 316 = 00112 – 3 строка, 116 = 00012 – 4 строка. Матрицей смежности ребер неориентированного графа G называется квадратная матрица A*(G) = [a*ij] порядка q, элементы a*ij которой равны единице, если ребра Так как в условии сказано, что граф не содержит в себе петель, то элементы диагонали в матрице смежности будут нули. Так как в условии сказано, что граф неориентированный, то воспользуемся еще одной особенностью матрицы смежности – симметричностью относительно главной диагонали. Таким образом, получим матрицу смежности: Построим граф: Степени вершин: D(a) = 3; d(b) = 2; d(c) = 4; D(d) = 2; d(f) = 3. Построим матрицу инциденций. Матрицей инцидентности (инциденций) неориентированного графа называется матрица Инцидентность – отношение между ребром и его концевыми вершинами, т. е. если в графе Итак, матрица инциденций примет вид: 2) Построить взвешенный (веса устанавливаются произвольно) ориентированный граф с 5-ю вершинами так, чтобы существовал эйлеров цикл. Найти кратчайшие маршруты, соединяющие все вершины. Решение: Эйлеровым путем в графе называется путь, проходящий по всем ребрам графа ровно по разу. Эйлеровым циклом называется такой тип эйлерова пути, в котором начальная и конечная вершины совпадают (то есть, здесь образуется цикл и в нем начальной вершиной Можно считать любую). Построим граф. Чтобы в конечном ориентированном графе существовал Эйлеров цикл, необходимо и достаточно равенство степеней вершин этого графа по входящим и выходящим ребрам. Это условие выполняется, следовательно, в построенном графе есть эйлеров цикл. Найдем кратчайшие маршруты, соединяющие все вершины. Минимальное количество ребер, соединяющих 5 вершины графа равно 4. Значит, найдем все возможные маршруты, состоящие из 4-х ребер. III. Деревья 1) Имеется K Городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (K-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна? Примечание: Использовать алгоритм поиска минимального остовного дерева (Прима, Крускала или др.). Выбранный алгоритм представить. Решение: Построим граф, состоящий из 5 вершин (городов) и ребер с весами (дорогами между данными городами с расстоянием между ними). Воспользуемся алгоритмом Краскала. Вход: связный взвешенный граф (G, φ) с неотрицательными весами. Выход: список T ребер каркаса минимального веса в G. 1. Положить 2. Выбрать в S ребро e минимального веса и удалить из S. 3. Если e не образует цикла с ребрами из T, добавить e в T. 4. Если список S не пуст, вернуться на шаг 2. Положим (v1,v5), (v4,v5), (v1,v4), (v2,v3), (v1,v2), (v3,v5), (v2,v4), (v1,v3) , (v2,v5), (v3,v4). Действуя по алгоритму, последовательно поместим в T ребра: (v1,v5) и (v4,v5). На следующем шаге из списка будет взято ребро (v1,v4); оно образует с ранее выбранными ребрами цикл v1 → v4 → v5, и не добавляется в T. На двух следующих шагах в T будут добавлены ребра (v2,v3), (v1,v2), после чего в T окажется требуемое для каркаса число ребер (4) и алгоритм можно будет остановить. В результате получим каркас исходного графа, который и является каркасом наименьшего веса (16) в исходном графе. (v1,v5), (v4,v5), (v2,v3), (v1,v2). Значит, именно таким образом нужно соединить города, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна. IV. Комбинаторика 1) Сколькими способами можно переставить буквы в вашей фамилии (учитывая, что буквы могут повторяться)? Решение: Так как в моей фамилии повторяющихся букв нет, то применим формулу перестановок без повторений: Ответ: в моей фамилии можно переставить буквы 120 способами. 2) На плоскости расположены k+n точек, из которых никакие три не лежат на одной прямой. Сколько различных прямых можно провести через эти точки? Решение: k + n = 11; Так как прямую однозначно можно провести только через две точки, то: Ответ: Через данные одиннадцать точек можно провести 55 различных прямых.
|