Сборник контрольных заданий по дискретной математике
Часть 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
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. а) Написать таблицу состояний данного автомата.
б) Считая автомат неинициальным, построить эквивалентный автомат Мура. Проверить работу данного и построенного автоматов над одним и тем же словом.
Вариант 3
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
|
|
|
|
|
|
|
|
|
|
|
|
|
| |