§ 44. Графы

§ 44. Графы 

1. Напишите программу,  которая вводит из файла весовую матрицу
   графа и строит для него минимальное остовное дерево.
2. Оцените асимптотическую сложность алгоритма Прима-Крускала.
3. Напишите программу,  которая  вводит из файла весовую матрицу
   графа, затем вводит с клавиатуры номера начальной и конечной вер­
   шин и определяет кратчайший маршрут.
4. Напишите программу,  которая вводит из файла весовую матрицу
   графа и определяет длины всех кратчайших маршрутов с помощью
   алгоритма Флойда-Уоршелла.
5. Оцените асимптотическую сложность алгоритмов Дейкстры и Флой­
   да-Уоршелла.
6. Напишите программу, которая решает задачу коммивояжёра для 5
   городов методом полного перебора. Можно ли использовать её для 50
   городов?

*7. Напишите программу, которая решает задачу 5 (о размещении шко­лы). Для определения кратчайших путей используйте алгоритм Флойда-Уоршелла. Весовую матрицу графа вводите из файла.