|
 Архив разработки (116 Кб, Mathcad-документ)
В данной работе для визуализации графов используется программа Шумилкиной Елены и Смирновой Ольги (см. банк студенческих задач).
Работа посвящена анализу внешней устойчивости и покрытий в графах.
Функция S1 предназначена для поиска множества внешне устойчивых вершин графа. Алгоритм поиска основан на вычислении степеней вершин графа и выборе вершины с наибольшей степенью в качестве доминирующей.
Функция Р подсчитывает номера вершин в вершинном покрытии. При этом число вершинного покрытия определяется как длина вектора Р. Функция Р1 определяет номера рёбер в рёберном покрытии, длина вектора Р1-число рёберного покрытия. Функция Н осуществляет генерацию матрицы смежности ориентированного графа. Функция S2 определяет множество внешнеустойчивых вершин ориентированного графа.
|
Генерация матрицы смежности M(G).
|
Все вычисления производятся для следующей матрицы смежности:
|
Вычисляем множество внешне устойчивых вершин S1 графа G. Определяем, является ли множество S1 ядром графа.
|
|
список степеней вершин
сумма элементов в столбце матрицы М
номер вершины с max степенью (Nv)
запись в V смежных вершине
Nv
Вычисляем число наблюдаемых из вершины четыре вершин в графе.
запись в матрицу М1 строки
и столбца с нулями
проверка на выход путём
сложения V и VT, содержащим
вершины которых нет в V
если в их сумме нет нулей то выход
|
 - множество внешне устойчивых вершин
Вычисление числа вершинного b0 и реберного b1 покрытия графа G.
|
|
Вычисление эксцентриситетов вершин
присваиваем элементам матрицы значение 1
В N1 заносим столбец матрицы N
N1 - новая матрица
Сравниваем N1 с 0
|
|
подсчитывает сумму столбцов матрицы
|
|
|
|
|
|
|
матр. инцидентности +1
|
|
|
|
|
|
Организуем цикл, в котором сравниваем элементы матрицы с нулём.
Если элемент или следующий за ним равен нулю,то переменную first увеличиваем на единицу,а stp увеличиваем на единицу, если элемент матрицы не равен нулю.
Далее сравнение происходит с переменной first. Для вычисления вектора Otv его элементу присваивают значение i, если переменная first не равна нулю.
|
|
|
номера вершин в вершинном покрытии
|
|
|
По аналогии с функцией Р находится переменная Otv.
|
|
 
 
|
номера рёбер в рёберном покрытии
|
|
Выполняем генерацию матрицы смежности M ориентированного помеченного графа H.
|
|
|
Объявление переменной с помощью генератора случайных чисел
Элементу матрицы присваивается 1, если x больше или равно 0.5 .
|
|
|
|
Вычисляем доминирующее множество вершин S2 графа H. Определяем, является ли множество S2 ядром орграфа.
Матрица А нужна для определения доминирующего множества вершин
подмножества S
 м-во дуг орграфа
|
|
Организовываются два цикла:
- внешний вычисляет доминирующее множество вершин.
- внутренний вычисляет степени эл-тов матрицы, сравнивает их с минимальной,
а в ответ заносит вершины с минимальной степенью меньше -1
Если же минимальная степень больше или равна -1,то осущесвляется еще один цикл, в котором рассматриваются элементы матрицы равные -1(1).
|
 - доминирующее множество вершин S2
|
