Вариант № 8.

Задание 1. Без учета ориентации и длин ребер графа выполнить следующее:

1.1.   а) Составить таблицу расстояний между вершинами графа, применяя волновой           метод.

        б) Указать условные радиусы, радиус, центры и диаметр графа.

1.2.   Найти наименьшее число цепей, в совокупности которых каждое ребро графа содержится ровно один раз, используя алгоритма Флери.

1.3.   По правилу Терри построить двойной эйлеров цикл.

1.4. Найти:

а) цикломатическое число g.

б) число внутренней устойчивости a.

в) число внешней устойчивости b.

г) хроматическое число q.

1.5.   Определить, существует ли в данном графе гамильтонов цикл или гамильтоновы цепи.

1.6. Построить граф с заданным набором степеней вершин.

Задание 2. Без учета ориентации, но с учетом длин ребер:

2.1. Найти расстояние от всех вершин графа до вершины   х₀ методом редукции индексов

2.2. С помощью алгоритма Краскала построить связный суграф наименьшего веса.

Задание III. С учетом ориентации и длин ребер.

3.3.   С помощью алгоритма Форда-Фалкерсона найти наибольший поток из x₀ в z₀.

3.4.   Построить критический разрез.

Вы можете заказать другой вариант или другие сочетания номеров данной контрольной работы, а также любую другую работу здесь.