Минимизация графовых моделей алгоритмических систем

Abstract

Рассматривается задача минимизации ориентированных графов с отмеченными вершинами. Задача минимизации заключается в нахождении разбиения всех вершин графа на классы эквивалентных вершин. Выделены новые классы графов состоящих из одной компоненты сильной связности. Предложены алгоритмы минимизации таких классов графов временной сложности O(e), где e – число ребер графа. Все алгоритмы корректны и выполняют правильное разбиение на классы эквивалентных вершин.