Дискретная математика 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.

Построим матрицу инциденций.

Матрицей инцидентности (инциденций) неориентированного графа называется матрица $i (|v| \times |e|)$ , для которой $i_{i,j} = 1$ , если вершина инцидентна ребру , в противном случае $i_{i,j} = 0$ .

Инцидентность – отношение между ребром и его концевыми вершинами, т. е. если в графе $g = (v,e), u \in v, v \in v$ — вершины, а $e \in e, e = (u,v)$ — соединяющее их ребро, то вершина и ребро инцидентны, вершина и ребро также инцидентны.

Итак, матрица инциденций примет вид:

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 различных прямых.

< Предыдущая Следующая >

Главное меню

Дискретная математика 07

II. Теория графов