Домашняя контрольная-5. Графы. Максимум 5 баллов.

Ваш вариант соответствует Вашему номеру в списке группы. Если номер от 1 до 5 – то вариант 1-5, если от 6 до 10, то 6 номеру в списке соответствует опять первый вариант, и т.д.

Задание 1. Для графа, представленного следующей матрицей инцидентности, определите матрицу смежности графа и изобразите его графически.

Вариант 1. Вариант 2.

Вариант 3. Вариант 4. Вариант 5.

Задание 2. Для графа, представленного следующей матрицей смежности, определите матрицу инцидентности графа и изобразите его графически.

Вариант 1. Вариант 2. Вариант 3.

Вариант 4. Вариант 5.

 

 

Задание 3. Пусть заданы два графа G₁(V₁,E₁), G₂(V₂, Е₂). Найдите матрицы смежности и инцидентности графов G₁U G₂; G₁U G₂ и G₁ G₂ Изобразите геометрически объединение графов G₁U G₂; пересечение графов G₁U G₂ и сумму по модулю два G₁ G₂. Для графа G₁

вычислите матрицу достижимости с помощью перемножения матриц и с помощью алгоритма Уоршелла.

Вариант 1

 

 

Вариант 2

 

 

Вариант 3

 

 

 

 

Вариант 4

 

 

 

Вариант 5

 

 

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

Домашняя контрольная-5а. Деревья. Максимум 5 баллов.

1. С помощью алгоритма вставки создать двоичное дерево поиска, присоединяя слова фразы «Я обязательно сдам дискретную математику» а) в том порядке, в котором они стоят в фразе, б) в обратном порядке.

2. Вставьте в это дерево слово «на» и затем слово «отлично».

3. Проследите за работой алгоритма поиска на примере обоих деревьев для поиска слова «на». Сколько операций сравнения понадобится а) в случае а), б) в случае б)?

4. Выпишите результат работы алгоритма правильного обхода на примере обоих деревьев.

5. Можете ли вы запрограммировать эти алгоритмы на тех языках программирования, что вы знаете?

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

Домашняя контрольная-6а. Коммуникационные сети. Максимум 5 баллов.

Вариант= Вашему номеру в списке группы

Для упражнений возьмите значения i, k, l, а, b из следующей таблицы согласно Вашему варианту

вар

i

k

l

a

b

Для графа коммуникационных сетей

 

1. C помощью алгоритма Дейкстры найдите кратчайшие пути от узла i до всех остальных узлов, изобразите дерево кратчайших путей и заполните таблицу маршрутов узла.

 

2. Какими будут дерево кратчайших путей между узлами и таблица маршрутов, если удалить обе линии связи между узлами k и l?

 

3. Какими будут дерево кратчайших путей между узлами и таблица маршрутов, если скорость передачи информации между узлами a и b уменьшится до 2?