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

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

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

e1

e2

e3

e4

e5

e6

e7

e8

e9

e10

e11

e12

e13

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

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

Вариант 16