Контрольная работа по предмету Высшая математика на тему: Комбинаторные алгоритмы. Вариант 1

Домашняя контрольная работа
Комбинаторные алгоритмы
Вариант 1
1. Запишите массив смежности для следующего графа
2. В каком порядке алгоритм поиска в ширину может посетить вершины графа, начиная с вершины 0?
3. Проиллюстрируйте работу алгоритма Борувки-Краскала на примере графа,
4. Как отработает алгоритм Ярника-Прима-Дейкстры на том же графе?
5. Проиллюстрируйте работу алгоритма Форда-Беллмана для поиска кратчайших путей от вершины номер 6 до всех остальных вершин следующего графа:
6. Проиллюстрируйте работу алгоритма Дейкстры для поиска кратчайших путей от вершины номер 1 до всех остальных вершин следующего графа:
7. Найдите максимальный поток в следующей сети
8. В некотором городке планируется строительство метрополитена. Городок стоит на многочисленных островах, некоторые из которых соединены тоннелями или мостами. Метро должно быть проложено с использованием имеющихся тоннелей и мостов. При этом прокладка линии по любому мосту существенно дороже, чем по любому тоннелю. Требуется спланировать прокладку линий так, чтобы жители города могли добраться на метро (возможно, с пересадками) с любого острова на любой другой. Известно, что имеющихся мостов и тоннелей для этого достаточно. Из соображений экономии было решено построить как можно меньше переездов между островами и использовать как можно меньше мостов.
Опишите математическую модель этой задачи как задачи на графе и опишите в неформализованном виде алгоритм решения.