О поиске минимальных вершинных расширений цветного неориентированного графа

Актуальность и цели. Предлагаются к рассмотрению результаты поиска минимальных вершинных расширений для неориентированных цветных графов. Данная тематика непосредственно связана с моделированием полных отказоустойчивых технических систем с элементами различного типа в терминологии графов. Система может быть описана некоторым графом, вершины которого сопоставлены некоторым элементам системы, а ребра - связям между ними. Отказоустойчивость является одним из важнейших свойств технических систем, особенно если данные системы введены в критические области жизни: медицина, освоение космоса, средства коммуникации. Материалы и методы. Используются методы математического моделирования технических систем в терминах теории графов. Основное исследование сосредоточено на построении попарно-неизоморфных отказоустойчивых реализаций цветных графов. При построении данных реализаций использованы техники isomorphism rejection и метод канонических представителей. Результаты. Рассматривается задача поиска минимальных вершинных k-расширений цветного графа без проверки на изоморфизм. Предлагается алгоритм поиска множества всех неизоморфных минимальных k-расширений для заданного цветного графа. Выводы. Представленный алгоритм был реализован в программном комплексе. Были проведены вычислительные эксперименты для различных конфигураций цветных графов.