Сборник контрольных заданий по дискретной математике

Часть 2

Вариант 1

1. С помощью алгоритма Дейкстры найти путь минимального веса между вершинами s и t в нагруженном графе.

2. Найти максимальный поток в заданной транспортной сети, используя алгоритм Форда-Фалкерсона. Проверить ответ по теореме Форда-Фалкерсона (найти минимальный разрез графа сети).

3. По матрице инцидентности построить остовное дерево графа. Составить список ветвей и хорд графа. Построить граф.

e1

e2

e3

e4

e5

e6

e7

e8

e9

e10

e11

e12

e13

1

2

3

4

5

6

7

8

4. а) Написать таблицу состояний данного автомата.

б) Считая автомат неинициальным, построить эквивалентный автомат Мура. Проверить работу данного и построенного автоматов над одним и тем же словом.

Вариант 2