Минимальные вершинные расширения цветных полных графов

Аннотация

Предлагаются к рассмотрению результаты поиска минимальных вершинных расширений для неориентированных цветных полных графов. Данная тематика непосредственно связана с моделированием полных отказоустойчивых технических систем с элементами различного типа в терминологии графов. Если описывать техническую систему как Σ, то ей сопоставляется некоторый граф G(Σ), в котором вершины соответствуют элементам системы Σ, а ребра – связям между ними. Тип каждого элемента выражается в сопоставлении каждой вершине графа G(Σ) некоторого цвета из множества цветов F = {1, 2…, i}. Вершинным расширением данной системы тогда является некоторый граф G(Σ), в котором введены избыточные вершины и при котором система, ему соответствующая, способна продолжать работу в присутствии k отказов любых её элементов. Полным граф называется тогда, когда любые две его вершины соединены ребром. Полные графы не имеют реберных расширений по определению – не существует способа добавить ребро в граф с максимальным количеством ребер. Другими словами, система, представленная полным графом, не способна противостоять отказам связей между своими элементами. Поэтому данная работа целиком посвящена исследованию минимальных вершинных расширений. Описываются условия существования минимальных вершинных расширений для цветных полных графов, приводятся схемы построения и формулы, по которым можно вычислить необходимое количество дополнительных ребер для построения минимального вершинного расширения цветного полного графа.