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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 29.04.2024

Просмотров: 24

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

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

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



Вариант 26

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. а) Написать таблицу состояний данного автомата.

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



Вариант 27

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






































1   2   3   4   5   6   7   8   9   10   11

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

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



Вариант 28

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. а) Написать таблицу состояний данного автомата.

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



Вариант 29

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



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



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



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

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



Вариант 30

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



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



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



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

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



Решение типового варианта

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



Решение.

Полагаем:

1 итерация: текущая вершина с постоянной меткой , далее расставляем метки у вершин, достижимых из s



В скобках указана та вершина, через которую модифицируется метка рассматриваемой вершины (на первой итерации везде стоит вершина s). Звездочкой отмечена наименьшая метка из чисел 4, 10, 11. При этом данная метка будет постоянной (в нашем случае 4).

2 итерация: текущая вершина с постоянной меткой , далее меняем метки у вершин с временными метками (меняются лишь метки тех вершин, которые достижимы из вершины y)



Метка а, стоящая в скобке в строчке для , означает, что путь из s в b, проходящий через вершину а, короче пути, состоящего из одной дуги . Аналогично в двух других случаях (2 и 4 строка).

3 итерация: текущая вершина с постоянной меткой ,



4 итерация: текущая вершина с постоянной меткой ,



Имеем 2 одинаковые метки с минимальным значением, поэтому выбираем любую из них (в данном случае )

5 итерация: текущая вершина с постоянной меткой ,

Смотрите также файлы