1. Составить матрицу смежности неориентированного графа.
2. С помощью волнового метода определить условные радиусы графа относительно всех вершин, радиус, диаметр и центры графа.
3. Методом редукции индекса найти расстояние от вершины 1 до всех остальных вершин графа и от всех вершин – до вершины с максимальным номером N . Указать цепи минимальной длины 1 − N и 2 − N .
4. С помощью алгоритма Флери построить, если возможно, эйлеров цикл (эйлерову цепь) в графе.
5. Используя алгоритм Тэрри, построить в графе двойной эйлеров цикл, начиная с вершины 1.
6. С помощью алгоритма Краскала построить остов графа наименьшего веса и определить его вес.
1. Построить матрицу смежности ориентированного графа.
2. Методом редукции индекса определить расстояние от вершины 1 до всех остальных вершин графа и от всех вершин до вершины N . Указать цепи минимальной длины 1 − N и 2 − N .
3. Решить задачу сетевого планирования:
• составить план работ, соответствующий сетевому графику G ;
• перенумеровать вершины с целью получения правильной нумерации;
• определить ранние сроки наступления событий Р i T ;
• определить ранние сроки окончания работ POij t ;
• указать критическое время и критический путь;
• найти поздние сроки наступления событий Пj T ;
• определить поздние сроки начала работ ПНij t ;
• найти полный Rij и свободный ij r резервы времени работ.
4. С помощью алгоритма Форда-Фалкерсона найти максимальный поток Фmax на транспортной сети и указать критическое сечение.