Дискретная математика 07
Контрольная работа
2) В таблице приведены запросы и количество найденных по ним страниц в Интернете.
Запрос |
Найдено страниц (тыс.) |
Шереметьево и Домодедово |
100n (600) |
Домодедово и Внуково |
50m (600) |
Шереметьево и Домодедово и Внуково |
20k (100) |
Какое число страниц (тыс.) будет найдено по запросу:
(Шереметьево и Домодедово) или (Домодедово и Внуково)
(Шереметьево и Домодедово) или (Домодедово и Внуково) =
=
Ответ: по данному запросу будет найдено 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. Положить ; выписать все ребра из G в список S по возрастанию веса.
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 различных прямых.
< Предыдущая | Следующая > |
---|