Контрольная работа по дискретной математике 1 семестр (стр. 7 )

. (1)

Аналогично, на множестве вершин, смежных с , найдем такую , что , и так далее.

После некоторого числа шагов вершина совпадает с вершиной , путь — кратчайший, а его длина .

Решим задачу по алгоритму Дейкстры (каждый шаг — присвоение одной постоянной метки).

1 шаг. . — постоянная метка.

— временные метки.

2 шаг.

Метка — наименьшая из всех временных меток, делаем ее постоянной.

— постоянная метка.

3 шаг.

Наименьшие из всех временных меток имеют вершины и . Выбираем, например, .

— постоянная метка.

4 шаг.

.

Метки не изменились, наименьшей из всех временных осталась метка 3, принадлежащая вершине .

— постоянная метка.

5 шаг.

.

— постоянная метка.

6 шаг.

.

— постоянная метка.

7 шаг.

— постоянная метка.

8 шаг.

— постоянная метка.

9 шаг.

.

— постоянная метка.

10 шаг. Последняя вершина получает последнюю постоянную метку

— постоянная метка.

Строим путь, начиная с конечной вершины. Из вершин и , смежных с , выбираем ту, для которой выполняется равенство (1):

для :

9=8+1 верно;

для :

9=6+4 неверно.

Значит, выбираем вершину .

Из вершин, смежных с выбираем ту, для которой выполняется равенство (1). Это будет вершина .

Из вершин, смежных с выбираем ту, для которой выполняется равенство (1). Это могут быть вершины и , оставим . Вершина смежна и выполняется равенство (1). Значит, кратчайший путь от до :

а длина его (вес) равна метке вершины , то есть 9.

Контрольная работа по дискретной математике Специальность 230100.62

Вариант 1

Задача 1. Докажите, что при любом натуральном имеет место равенство

.

Задача 2. Для проведения письменного экзамена по дискретной математике надо составить 4 варианта по 7 задач в каждом. Сколькими способами можно разбить 28 задач на 4 варианта?

Задача 3. Найдите коэффициент при в разложении .

Задача 4. Даны числовые множества и . Найдите , , , , , и . Изобразите .

а) ,

б) , где — множество цифр .